# A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree

arXiv: https://arxiv.org/abs/2111.15478 · HTML: https://mlsanity.com/paper/2111.15478/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2021.

## Built on by (most cited first, 8 of 8)

- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Incremental Extractive Opinion Summarization Using Cover Trees](https://mlsanity.com/paper/2401.08047/) (2024)
- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [Material Property Prediction using Graphs based on Generically Complete Isometry Invariants](https://mlsanity.com/paper/2212.11246/) (2022)
- [Inorganic synthesis-structure maps in zeolites with machine learning and crystallographic distances](https://mlsanity.com/paper/2307.10935/) (2023)
- [Accelerating Non-Maximum Suppression: A Graph Theory Perspective](https://mlsanity.com/paper/2409.20520/) (2024)
- [Vecchia-Inducing-Points Full-Scale Approximations for Gaussian Processes](https://mlsanity.com/paper/2507.05064/) (2025)
- [KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees](https://mlsanity.com/paper/2610.16940/) (2026)

## Abstract (arXiv)

Given a reference set R of n points and a query set Q of m points in a metric space, this paper studies an important problem of finding k-nearest neighbors of every point q ∈ Q in the set R in a near-linear time. In the paper at ICML 2006, Beygelzimer, Kakade, and Langford introduced a cover tree on R and attempted to prove that this tree can be built in O(nlog n) time while the nearest neighbor search can be done in O(nlog m) time with a hidden dimensionality factor. This paper fills a substantial gap in the past proofs of time complexity by defining a simpler compressed cover tree on the reference set R. The first new algorithm constructs a compressed cover tree in O(n log n) time. The second new algorithm finds all k-nearest neighbors of all points from Q using a compressed cover tree in time O(m(k+log n)log k) with a hidden dimensionality factor depending on point distributions of the given sets R,Q but not on their sizes.