Sankowski, Piotr ;
Wygocki, Piotr
Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}
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 capproximate 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 polylogarithmic query time and polynomial
preprocessing 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 capproximate 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  Entry
@InProceedings{sankowski_et_al:LIPIcs:2017:8218,
author = {Piotr Sankowski and Piotr Wygocki},
title = {{Approximate Nearest Neighbors Search Without False Negatives For l_2 For c>sqrt{loglog{n}}}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {63:163:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8218},
URN = {urn:nbn:de:0030drops82189},
doi = {10.4230/LIPIcs.ISAAC.2017.63},
annote = {Keywords: locality sensitive hashing, approximate near neighbor search, high dimensional, similarity search}
}
07.12.2017
Keywords: 

locality sensitive hashing, approximate near neighbor search, high dimensional, similarity search 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 