Locality-sensitive Hashing Without False Negatives For L_p

Pacuk Andrzej, Sankowski Piotr, Wegrzycki Karol, Wygocki Piotr. Computing and Combinatorics - 2016

[Paper]    
Independent

In this paper, we show a construction of locality-sensitive hash functions without false negatives, i.e., which ensure collision for every pair of points within a given radius $R$ in $d$ dimensional space equipped with $l_p$ norm when $p\in [1,\mathrm{\infty }]$. Furthermore, we show how to use these hash functions to solve the $c$-approximate nearest neighbor search problem without false negatives. Namely, if there is a point at distance $R$, we will certainly report it and points at distance greater than $cR$ will not be reported for $c=\Omega (\sqrt{d},d^{1-\frac{1}{p}})$. The constructed algorithms work: - with preprocessing time $\mathcal{O}(nlog(n))$ and sublinear expected query time,

• with preprocessing time $\mathcal{O}(\mathrm{poly}(n))$ and expected query time $\mathcal{O}(log(n))$. Our paper reports progress on answering the open problem presented by Pagh [8] who considered the nearest neighbor search without false negatives for the Hamming distance.

Similar Work

• Coveringlsh Locality-sensitive Hashing Without False Negatives
• Sparse Similarity-preserving Hashing
• Approximate Nearest Neighbors In Limited Space
• Near Neighbor Who Is The Fairest Of Them All