Fascinating paper on vp-trees, useful for generalized BSP indexing over metric spaces. Like a kd-tree but more flexible and abstract, and more useful on non-Euclidean distance metrics. I've been thinking about using vp-trees over a Levenshtein-distance metric space for some code complexity assessments--seems to have better performance than either a kd-tree, and more generality than a bk-tree.