Locality-sensitive Hashing without False Negatives

Rasmus Pagh

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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) 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. Read More: http://epubs.siam.org/doi/10.1137/1.9781611974331.ch1
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSociety for Industrial and Applied Mathematics
Publication date2016
ISBN (Electronic)978-1-61197-433-1
Publication statusPublished - 2016


  • Locality-Sensitive Hashing (LSH)
  • Hamming Space
  • Hash Function Construction
  • Collision Guarantee
  • Similarity Search


Dive into the research topics of 'Locality-sensitive Hashing without False Negatives'. Together they form a unique fingerprint.

Cite this