Vantage-point tree

A vantage-point tree (or VP tree) is a metric tree that segregates data in a metric space by choosing a position in the space (the 'vantage point') and partitioning the data points into two parts: those points that are nearer to the vantage point than a threshold, and those points that are not. By recursively 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. A vantage-point tree (or VP tree) is a metric tree that segregates data in a metric space by choosing a position in the space (the 'vantage point') and partitioning the data points into two parts: those points that are nearer to the vantage point than a threshold, and those points that are not. By recursively 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. One generalization is called a multi-vantage-point tree, or MVP tree: a data structure for indexing objects from large metric spaces for similarity search queries. It uses more than one point to partition each level. Peter Yianilos claimed that the vantage-point tree was discovered independently by him (Peter Yianilos)and by Jeffrey Uhlmann.Yet, Uhlmann published this method before Yianilos in 1991.Uhlmann called the data structure a metric tree, the name VP-tree wasproposed by Yianilos.Vantage-point trees have been generalized to non-metric spaces using Bregman divergences by Nielsen et al. 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 two-dimensional Euclidean space, this can be visualized as a series of circles segregating the data.