Approximate nearest neighbors search without false negatives for l₂ for c> n

DOI10.4230/LIPICS.ISAAC.2017.63MaRDI QIDQ5136284zbMATH OpenOpenAlexFDO

Authors Piotr Sankowski, Piotr Wygocki

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1708.06395

zbMATH Keywords

high-dimensionallocality sensitive hashingsimilarity searchapproximate near neighbor search

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Abstract: In this paper, we report progress on answering the open problem presented by Pagh~[14], who considered the nearest neighbor search without false negatives for the Hamming distance. We show new data structures for solving the $c$-approximate nearest neighbors problem without false negatives for Euclidean high dimensional space $mathcal{R}^d$. These data structures work for any $c=omega(sqrtloglogn)$, where $n$ is the number of points in the input set, with poly-logarithmic query time and polynomial preprocessing time. This improves over the known algorithms, which require $c$ to be $Omega(sqrtd)$. 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 nearest neighbor search instances in $$ space equipped with metric $m(x,y)=ma{x}_{1leileL}(lVert{x}_i-y_{i}Ver{t}_2)$.

Recommendations

• Locality-Sensitive Hashing Without False Negatives for $$l_p$$
• Beyond locality-sensitive hashing
• On approximate nearest neighbors under \(l_\infty\) norm
• scientific article; zbMATH DE number 1775450
• A locality-sensitive hash for real vectors

Cites work

• scientific article; zbMATH DE number 5485498 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Approximate range searching in higher dimension
• Extensions of Lipschitz mappings into a Hilbert space
• Locality-Sensitive Hashing Without False Negatives for $$l_p$$
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Optimal data-dependent hashing for approximate near neighbors

Cited in

(3)

• An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN
• An algorithm for reducing approximate nearest neighbor to approximate near neighbor with \(O(\log{n})\) query time
• Beyond locality-sensitive hashing

This page was built for publication: Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136284)