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.[1]
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.
[edit] References
- ^ Yianilos, Peter N. (1993). "Data structures and algorithms for nearest neighbor search in general metric spaces". Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 311–321. pny93. http://pnylab.com/pny/papers/vptree/vptree/. Retrieved 2008-08-22.
|
||||||||||||||||||||||||||
 |
This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
