Projects per year
Abstract
We present an I/Oefficient algorithm for computing similarity
joins based on localitysensitive hashing (LSH). In contrast to the filtering
methods commonly suggested our method has provable subquadratic
dependency on the data size. Further, in contrast to straightforward
implementations of known LSHbased algorithms on external memory,
our approach is able to take significant advantage of the available internal
memory: Whereas the time complexity of classical algorithms includes a
factor of N ρ, where ρ is a parameter of the LSH used, the I/O complexity
of our algorithm merely includes a factor (N/M)ρ, where N is the data size
and M is the size of internal memory. Our algorithm is randomized and
outputs the correct result with high probability. It is a simple, recursive,
cacheoblivious procedure, and we believe that it will be useful also in
other computational settings such as parallel computation.
joins based on localitysensitive hashing (LSH). In contrast to the filtering
methods commonly suggested our method has provable subquadratic
dependency on the data size. Further, in contrast to straightforward
implementations of known LSHbased algorithms on external memory,
our approach is able to take significant advantage of the available internal
memory: Whereas the time complexity of classical algorithms includes a
factor of N ρ, where ρ is a parameter of the LSH used, the I/O complexity
of our algorithm merely includes a factor (N/M)ρ, where N is the data size
and M is the size of internal memory. Our algorithm is randomized and
outputs the correct result with high probability. It is a simple, recursive,
cacheoblivious procedure, and we believe that it will be useful also in
other computational settings such as parallel computation.
Original language  English 

Title of host publication  Algorithms  ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 1416, 2015, Proceedings 
Number of pages  12 
Publisher  Springer 
Publication date  14 Sept 2015 
Pages  941952 
ISBN (Print)  9783662483497 
ISBN (Electronic)  9783662483503 
DOIs  
Publication status  Published  14 Sept 2015 
Series  Lecture Notes in Computer Science 

Volume  9294 
ISSN  03029743 
Keywords
 I/Oefficient algorithms
 Localitysensitive hashing
 Similarity joins
 Cacheoblivious computing
 External memory algorithms
Fingerprint
Dive into the research topics of 'I/OEfficient Similarity Join'. 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