Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}
Lists
Only you see this
Abstract
In this paper, we report progress on answering the open problem presented by Pagh [11], who considered the near neighbor search without false negatives for the Hamming distance. We show new data structures for solving the c-approximate near neighbors problem without false negatives for Euclidean high dimensional space \mathcal{R}^d. These data structures work for any c = \omega(\sqrt{\log{\log{n}}}), where n is the number of points in the input set, with poly-logarithmic query time and polynomial pre-processing time. This improves over the known algorithms, which require c to be \Omega(\sqrt{d}). This improvement is obtained by applying a sequence of reductions, which are interesting on their own. First, we reduce the problem to d instances of dimension logarithmic in n. Next, these instances are reduced to a number of c-approximate near neighbor search without false negatives instances in \big(\Rspace^k\big)^L space equipped with metric m(x,y) = \max_{1 \le i \leL}(\dist{x_i - y_i}_2).
BibTeX
@inproceedings{sankowski2017approximate,
author = {Piotr Sankowski and Piotr Wygocki},
title = {{Approximate Nearest Neighbors Search Without False Negatives For l\_2 For c>sqrt\{loglog\{n\}\}}},
booktitle = {ISAAC},
year = {2017},
url = {https://openreview.net/forum?id=fVfzGnh32b},
}