Name
Abstract | ||
|---|---|---|
We present an I/O-efficient algorithm for computing similarity joins based on locality-sensitive hashing (LSH). In contrast to the filtering methods commonly suggested our method has provable sub-quadratic dependency on the data size. Further, in contrast to straightforward implementations of known LSH-based 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^\\rho $$N¿, where $$\\rho $$¿ is a parameter of the LSH used, the I/O complexity of our algorithm merely includes a factor $$(N/M)^\\rho $$(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, cache-oblivious procedure, and we believe that it will be useful also in other computational settings such as parallel computation. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00453-017-0285-5 | Algorithmica |
Keywords | Field | DocType |
Similarity join,Locality sensitive hashing,Cache aware,Cache oblivious | Locality-sensitive hashing,Discrete mathematics,Joins,Cache-oblivious algorithm,Combinatorics,Computer science,Input/output,Hash function,Time complexity,Recursion,Auxiliary memory | Journal |
Volume | Issue | ISSN |
78 | 4 | 0178-4617 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rasmus Pagh | 1 | 1344 | 86.08 |
| Ninh Pham | 2 | 169 | 7.68 |
| Francesco Silvestri 0001 | 3 | 172 | 14.44 |
| Morten Stöckel | 4 | 19 | 3.80 |