Improved approximate near neighbor search without false negatives for l_2
share
We present a new algorithm for the c--approximate nearest neighbor search without false negatives for l_2^d. We enhance the dimension reduction method presented in wygos_red and combine it with the standard results of Indyk and Motwani motwani. We present an efficient algorithm with Las Vegas guaranties for any c>1. This improves over the previous results, which require c=ω(n) wygos_red, 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(d^2) 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).
READ FULL TEXT