Perform a nearest neighbor search based on a vantage point (VP) tree. More...
#include <Vptree.hpp>
Public Member Functions | |
| Prebuilt< typename Matrix_::dimension_type, typename Matrix_::index_type, Float_ > * | build_raw (const Matrix_ &data) const |
 Public Member Functions inherited from knncolle::Builder< Matrix_, Float_ > | |
| std::shared_ptr< Prebuilt< typename Matrix_::dimension_type, typename Matrix_::index_type, Float_ > > | build_shared (const Matrix_ &data) const |
| std::unique_ptr< Prebuilt< typename Matrix_::dimension_type, typename Matrix_::index_type, Float_ > > | build_unique (const Matrix_ &data) const |
Detailed Description
class knncolle::VptreeBuilder< Distance_, Matrix_, Float_ >
Perform a nearest neighbor search based on a vantage point (VP) tree.
In a vantage point tree (Yianilos, 1993), each node contains a subset of points that is split into two further partitions. The split is determined by picking an arbitrary point inside that subset as the node center, computing the distance to all other points from the center, and using the median distance as the "radius" of a hypersphere. The left child of this node contains all points within that hypersphere while the right child contains the remaining points. This procedure is applied recursively until all points resolve to individual nodes, thus yielding a VP tree. Upon searching, the algorithm traverses the tree and exploits the triangle inequality between query points and node centers to narrow the search space.
The major advantage of VP trees over more conventional KD-trees or ball trees is that the former does not need to construct intermediate nodes, instead using the data points themselves at the nodes. This reduces the memory usage of the tree and total number of distance calculations for any search. It can also be very useful when the concept of an intermediate is not well-defined (e.g., for non-numeric data), though this is not particularly relevant for knncolle.
- Template Parameters
-
Distance_ Class to compute the distance between vectors, see distance::Euclideanfor an example.Matrix_ Matrix-like object satisfying the MockMatrixcontract.Float_ Floating point type for the query data and output distances.
- See also
- Yianilos PN (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 311-321.
- Hanov S (2011). VP trees: A data structure for finding stuff fast. http://stevehanov.ca/blog/index.php?id=130
Member Function Documentation
◆ build_raw()
|
inlinevirtual |
Creates a VptreePrebuilt instance.
Implements knncolle::Builder< Matrix_, Float_ >.
The documentation for this class was generated from the following file:
- knncolle/Vptree.hpp
