Locality-sensitive Hashing without False Negatives

 

Locality-sensitive Hashing without False Negatives by Rasmus Pagh

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c>1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (FOCS '98). The efficiency of the new construction essentially matches their bound if cr=log(n)/k, where n is the number of points in the data set and k∈N, and differs from it by at most a factor ln(4)<1.4 in the exponent for general values of cr. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

  Credits: ESA/Rosetta/MPS for OSIRIS Team MPS/UPD/LAM/IAA/SSO/INTA/UPM/DASP/IDA

This image shows a portion of the Seth region on comet 67P/Churyumov-Gerasimenko, exhibiting a fractured scarp and a debris field at the foot of the cliff suggesting a progressive process of 'mass-wasting'.
The image was taken by Rosetta's OSIRIS narrow-angle camera.
An annotated version of the image with an indication of the physical scale is available here, as part of a composite image.


 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.