###
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.
## No comments:

Post a Comment