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 $\ell_2$ 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, matching the performance of~\cite{ tobias2016}. The algorithms are based on space partitions, as with classic LSH, but we construct these using a combination of brute force, tensoring, perfect hashing and splitter functions \`a la~\cite{ naor1995splitters}. We also show a new dimensionality reduction lemma with 1-sided error.
Categories: cs.DS