TY - JOUR

T1 - CoveringLSH: Locality-sensitive Hashing without False Negatives

AU - Pagh, Rasmus

PY - 2018

Y1 - 2018

N2 - 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 (STOC’98). The efficiency of the new construction essentially matches their bound when the search radius is not too large—e.g., when cr = o(log (n)/ log log n), where n is the number of points in the dataset, 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.

AB - 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 (STOC’98). The efficiency of the new construction essentially matches their bound when the search radius is not too large—e.g., when cr = o(log (n)/ log log n), where n is the number of points in the dataset, 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.

KW - recall

KW - locality-sensitive hashing

KW - high-dimensional

KW - Similarity search

KW - Theory of computation

U2 - 10.1145/3155300

DO - 10.1145/3155300

M3 - Journal article

SN - 1549-6325

VL - 14

JO - A C M Transactions on Algorithms

JF - A C M Transactions on Algorithms

IS - 3

M1 - 29

ER -