Projects per year
Abstract
We consider a new construction of localitysensitive 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, LSHbased 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 language  English 

Title of host publication  Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms 
Publisher  Society for Industrial and Applied Mathematics 
Publication date  2016 
Pages  19 
ISBN (Electronic)  9781611974331 
DOIs  
Publication status  Published  2016 
Keywords
 LocalitySensitive Hashing (LSH)
 Hamming Space
 Hash Function Construction
 Collision Guarantee
 Similarity Search
Fingerprint
Dive into the research topics of 'Localitysensitive Hashing without False Negatives'. Together they form a unique fingerprint.Projects
 1 Finished

SSS: Scalable Similarity Search
Pagh, R. (PI), Christiani, T. L. (CoI), Pham, N. D. (CoI), Faithfull, A. (CoI), Silvestri, F. (CoI), Mikkelsen, J. W. (CoI), Sivertsen, J. V. T. (CoI), Aumüller, M. (CoI), Skala, M. (CoI), Ceccarello, M. (CoI), Themsen, R. (CoI), Jacob, R. (CoI), McCauley, S. (CoI) & Ahle, T. D. (CoI)
01/05/2014 → 30/04/2019
Project: Research