Class CompressedCoverTree

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

Class Documentation

class CompressedCoverTree : public dim_red::NearestNeighbors

A new compressed cover tree guarantees a parameterized time complexity that is near-linear in the maximum size of both query and reference set.

References

  1. Yury Elkin. New compressed cover tree for k-nearest neighbor search. arXiv 2022.

Public Functions

CompressedCoverTree(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.

~CompressedCoverTree()
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}.

inline 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}.