Paper Info
Title
LSH banding for large-scale retrieval with memory and recall constraints
Abstract
Locality Sensitive Hashing (LSH) is widely used for efficient retrieval of candidate matches in very large audio, video, and image systems. However, extremely large reference databases necessitate a guaranteed limit on the memory used by the table lookup itself, no matter how the entries crowd different parts of the signature space, a guarantee that LSH does not give. In this paper, we provide such guaranteed limits, primarily through the design of the LSH bands. When combined with data-adaptive bin splitting (needed on only 0.04% of the occupied bins) this approach provides the required guarantee on memory usage. At the same time, it avoids the reduced recall that more extensive use of bin splitting would give.
Year
DOI
Venue
2009
10.1109/ICASSP.2009.4959971
ICASSP
Keywords
Field
DocType
locality sensitive hashing,bin splitting,fingerprint identification,lsh band,required guarantee,memory usage,large audio,index terms— multimedia databases,large-scale retrieval,lsh banding,information retrieval,guaranteed limit,large reference databases,occupied bin,data-adaptive bin splitting,pattern matching,fingerprint recognition,data mining,solids,image retrieval,probability density function,memory management,indexing terms,entropy,mutual information
Locality-sensitive hashing,Data mining,Pattern recognition,Bin,Computer science,Fingerprint,Memory management,Artificial intelligence,Recall,Probability density function,Pattern matching
Conference
ISSN
Citations 
PageRank 
1520-6149
8
0.49
References 
Authors
8
2
Name
Order
Citations
PageRank
Michele Covell170678.42
Shumeet Baluja24053728.83