knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ > Class Template Reference

Perform a nearest neighbor search based on a vantage point (VP) tree. More...

#include <Vptree.hpp>

Inheritance diagram for knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ >:

Collaboration diagram for knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ >:

Public Member Functions
	VptreeBuilder (std::shared_ptr< const DistanceMetric_ > metric)
	VptreeBuilder (const DistanceMetric_ *metric)
Prebuilt< Index_, Data_, Distance_ > *	build_raw (const Matrix_ &data) const
Public Member Functions inherited from knncolle::Builder< Index_, Data_, Distance_, Matrix_ >
std::shared_ptr< Prebuilt< Index_, Data_, Distance_ > >	build_shared (const Matrix_ &data) const
std::unique_ptr< Prebuilt< Index_, Data_, Distance_ > >	build_unique (const Matrix_ &data) const

Detailed Description

template<typename Index_, typename Data_, typename Distance_, class Matrix_ = Matrix<Index_, Data_>, class DistanceMetric_ = DistanceMetric<Data_, Distance_>>
class knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ >

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

Index_	Integer type for the observation indices.
Data_	Numeric type for the input and query data.
Distance_	Floating point type for the distances.
Matrix_	Class of the input data matrix. This should satisfy the Matrix interface.
DistanceMetric_	Class implementing the distance metric calculation. This should satisfy the DistanceMetric interface.

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

Constructor & Destructor Documentation

VptreeBuilder() [1/2]

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = Matrix<Index_, Data_>, class DistanceMetric_ = DistanceMetric<Data_, Distance_>>

knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ >::VptreeBuilder ( std::shared_ptr< const DistanceMetric_ > metric )

inline

Parameters

metric

Pointer to a distance metric instance, e.g., EuclideanDistance.

VptreeBuilder() [2/2]

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = Matrix<Index_, Data_>, class DistanceMetric_ = DistanceMetric<Data_, Distance_>>

knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ >::VptreeBuilder ( const DistanceMetric_ * metric )

inline

Parameters

metric

Pointer to a distance metric instance, e.g., EuclideanDistance.

Member Function Documentation

build_raw()

template<typename Index_ , typename Data_ , typename Distance_ , class Matrix_ = Matrix<Index_, Data_>, class DistanceMetric_ = DistanceMetric<Data_, Distance_>>

Prebuilt< Index_, Data_, Distance_ > * knncolle::VptreeBuilder< Index_, Data_, Distance_, Matrix_, DistanceMetric_ >::build_raw ( const Matrix_ & data ) const

inlinevirtual

Creates a VptreePrebuilt instance.

Implements knncolle::Builder< Index_, Data_, Distance_, Matrix_ >.

---

The documentation for this class was generated from the following file:

• knncolle/Vptree.hpp