Vantage-point tree

<p>A vantage-point tree (or VP tree) is a <a href="/facts/Metric_tree/wmyxmJ5x">metric tree</a> that segregates data in a <a href="/facts/Metric_space/gnBBRXtc">metric space</a> 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 <a href="/facts/Tree_(data_structure)/RcXz9noF">tree data structure</a> is created where neighbors in the tree are likely to be neighbors in the space.
</p><p>One generalization is called a multi-vantage-point tree (or MVP tree): a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> for indexing objects from large <a href="/facts/Metric_space/gnBBRXtc">metric spaces</a> for <a href="/facts/Nearest_neighbor_search/R6QTyAph">similarity search</a> queries. It uses more than one point to partition each level.
</p>

Vantage-point tree open-in-new

Vantage-point tree