Optimal Las Vegas Locality Sensitive Data Structures

Abstract

We show that approximate similarity (near neighbour) search can be solved in high dimensions with performance matching state of the art (data independent) Locality Sensitive Hashing, but with a guarantee of no false negatives. Specifically, we give two data structures for common problems. For \(c\)-approximate near neighbour in Hamming space we get query time \(dn^\{1/c+o(1)\}\) and space \(dn^\{1+1/c+o(1)\}\) matching that of \cite\{indyk1998approximate\} and answering a long standing open question from~\cite\{indyk2000dimensionality\} and~\cite\{pagh2016locality\} in the affirmative. By means of a new deterministic reduction from \(\ell_1\) to Hamming we also solve \(\ell_1\) and \(ℓ₂\) with query time \(d^2n^\{1/c+o(1)\}\) and space \(d^2 n^\{1+1/c+o(1)\}\). For \((s_1,s_2)\)-approximate Jaccard similarity we get query time \(dn^\{\rho+o(1)\}\) and space \(dn^\{1+\rho+o(1)\}\), \(\rho=log\frac\{1+s_1\}\{2s_1\}\big/log\frac\{1+s_2\}\{2s_2\}\), when sets have equal size, match

Stats

• citations7
• S2 citations—
• github stars0
• HF likes0
• heat score6.77
• arxiv keyahle2017optimal

Related papers

• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• On The Adversarial Robustness Of Locality-sensitive Hashing In Hamming Space (2024)2.26
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Approximate Nearest Neighbors Search Without False Negatives For \(l_2\) For \(c>\sqrt{\log\log{n}}\) (2017)0.00
• Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Hierarchical Locality Sensitive Hashing For Structured Data: A Survey (2022)0.00