Locality-sensitive hashing without false negatives

DOI10.1137/1.9781611974331.CH1zbMATH Open1410.68103arXiv1507.03225OpenAlexW2951895957MaRDI QIDQ4575575FDOQ4575575

Authors: Rasmus Pagh 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We consider a new construction of locality-sensitive hash functions for Hamming space that is emph{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 emph{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 (STOC '98). The efficiency of the new construction essentially emph{matches} their bound when the search radius is not too large --- e.g., when $cr=o(log(n)/loglogn)$, where $n$ is the number of points in the data set, and when $cr=log(n)/k$ where $k$ is an integer constant. In general, it differs by at most a factor $ln(4)$ in the exponent of the time bounds. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

Full work available at URL: https://arxiv.org/abs/1507.03225

Recommendations

• CoveringLSH: locality-sensitive hashing without false negatives
• Locality-Sensitive Hashing Without False Negatives for $$l_p$$
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Lower Bounds on Locality Sensitive Hashing
• On the Distortion of Locality Sensitive Hashing

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (23)

• Sharing hash codes for multiple purposes
• The complexity of LSH feasibility
• Covering codes for the fixed length Levenshtein metric
• Frequent-itemset mining using locality-sensitive hashing
• Fast cross-polytope locality-sensitive hashing
• The distortion of locality sensitive hashing
• LSH-preserving functions and their applications
• Locality-sensitive bucketing functions for the edit distance
• Why locality sensitive hashing works: a practical perspective
• CoveringLSH: locality-sensitive hashing without false negatives
• Locality sensitive hashing with extended differential privacy
• Title not available (Why is that?)
• Locality-Sensitive Hashing Without False Negatives for $$l_p$$
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Index structures for fast similarity search for binary vectors
• Lower Bounds on Locality Sensitive Hashing
• A locality sensitive hashing filter for encrypted vector databases
• Asymptotics and improvements of sieving for codes
• On the Distortion of Locality Sensitive Hashing
• I/O-efficient similarity join
• Set similarity search beyond MinHash
• LSH-preserving functions and their applications
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time

This page was built for publication: Locality-sensitive hashing without false negatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575575)