A New Near-linear Time Algorithm For K-nearest Neighbor Search Using A Compressed Cover Tree

Abstract

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 \in 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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyelkin2021a

Related papers

• Paired Compressed Cover Trees Guarantee A Near Linear Parametrized Complexity For All \(k\)-nearest Neighbors Search In An Arbitrary Metric Space (2022)0.00
• Counterexamples Expose Gaps In The Proof Of Time Complexity For Cover Trees Introduced In 2006 (2022)4.52
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• Improving Reverse K Nearest Neighbors Queries (2020)6.34
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00
• Efficient Autotuning Of Hyperparameters In Approximate Nearest Neighbor Search (2018)6.77