VP-tree

A vantage point tree, or vp-tree is a BSP tree that segregates data in a metric space by choosing a position in the space (the "vantage point") and dividing the data points into two partitions: those that are nearer to the vantage point than a threshold, and those that are not. By repeatedly applying this procedure to partition the data into smaller and smaller sets, a tree data structure is created where neighbors in the tree are likely to be neighbors in the space.cite conference
first = Peter N.
last = Yianilos
authorlink =
coauthors =
title = Data structures and algorithms for nearest neighbor search in general metric spaces
booktitle = Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms
pages = 311-321
publisher = Society for Industrial and Applied Mathematics Philadelphia, PA, USA
date = 1993
location =
url = http://pnylab.com/pny/papers/vptree/vptree/
accessdate = 2008-08-22
id = pny93]

This iterative partitioning process is similar to that of a k-d tree, but uses circular (or spherical, hyperspherical, etc) rather than rectilinear partitions. In 2D Euclidean space, this can be visualized as a series of circles segregating the data.

The vp-tree is particularly useful in dividing data in a non-standard metric space into a BSP tree.

References