An Algorithm For Reducing Approximate Nearest Neighbor To Approximate Near Neighbor With O(logn) Query Time

Abstract

This paper proposes a new algorithm for reducing Approximate Nearest Neighbor problem to Approximate Near Neighbor problem. The advantage of this algorithm is that it achieves O(log n) query time. As a reduction problem, the uery time complexity is the times of invoking the algorithm for Approximate Near Neighbor problem. All former algorithms for the same reduction need polylog(n) query time. A box split method proposed by Vaidya is used in our paper to achieve the O(log n) query time complexity.

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keyma2018an

Related papers

• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• A New Near-linear Time Algorithm For K-nearest Neighbor Search Using A Compressed Cover Tree (2021)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84
• Associative Memories To Accelerate Approximate Nearest Neighbor Search (2016)6.34