An Algorithm for Reducing Approximate Nearest Neighbor to Approximate Near Neighbor with O(logn) Query Time

2018/09/26 by Ma, Hengzhao, Li, Jianzhong
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1809.09776

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.

Related

• A Sub-linear Time Algorithm for Approximating k-Nearest-Neighbor with Full Quality Guarantee
• Improved approximate near neighbor search without false negatives for l₂
• Hardness of Approximate Nearest Neighbor Search
• Beyond Locality-Sensitive Hashing
• Approximate nearest neighbors search without false negatives for l₂ for c>√loglogn