2017/09/28 by Piotr Wygocki, Wygocki, Piotr
Computer Science · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1709.10338
openalex publication_date 2017/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new algorithm for the c--approximate nearest neighbor search without false negatives for l2d. We enhance the dimension reduction method presented in \citewygosred and combine it with the standard results of Indyk and Motwani~\citemotwani. We present an efficient algorithm with Las Vegas guaranties for any c>1. This improves over the previous results, which require c=ω(loglogn) \citewygosred, where n is the number of the input points. Moreover, we improve both the query time and the pre-processing time. Our algorithm is tunable, which allows for different compromises between the query and the pre-processing times. In order to illustrate this flexibility, we present two variants of the algorithm. The "efficient query" variant involves the query time of O(d2) and the polynomial pre-processing time. The "efficient pre-processing" variant involves the pre-processing time equal to O(dω-1 n) and the query time sub-linear in n, where ω is the exponent in the complexity of the fast matrix multiplication. In addition, we introduce batch versions of the mentioned algorithms, where the queries come in batches of size d. In this case, the amortized query time of the "efficient query" algorithm is reduced to O(dω-1).