Class CoverTree

Defined in File CoverTree.hpp

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

public dim_red::NearestNeighbors (Class NearestNeighbors)

Class Documentation

class CoverTree : public dim_red::NearestNeighbors 

Cover tree is a data structure for generic nearest neighbor search, which is especially efficient in spaces with small intrinsic dimension. The cover tree has a theoretical bound that is based on the dataset’s doubling constant. The bound on search time is O(c¹² log node) where c is the expansion constant of the dataset.

References

Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. ICML

Public Functions

CoverTree(const Eigen::Ref<const Matrix> &x, double base = 1.3, const std::string &metric = "euclidean")

Constructor.

Parameters

x – the dataset.
base – the base of the expansion constant.
metric – a metric distance measure for nearest neighbor search.

~CoverTree()

virtual std::pair<Vector, IntVector> query(const Eigen::Ref<const Vector> &point, int k, bool sort_results = true) const override

Retrieves the k-nearest neighbors for the query point.

Parameters

point – the query point.
k – the number of nearest neighbors to search for.
sort_results – if true, the neighbors will be sorted by distances in ascending order.

Returns

the k-nearest neighbors: {distances, indices}.

virtual std::pair<Vector, IntVector> queryRadius(const Eigen::Ref<const Vector> &point, double radius, bool sort_results = false) const override

Retrieves all the neighbors of the query point in the specified radius.

Parameters

point – the query point.
radius – the search radius.
sort_results – if true, the neighbors will be sorted by distances in ascending order.

Returns

the nearest neighbors in the specified radius: {distances, indices}.