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ρ, 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, cache-oblivious procedure, and we believe
that it will be useful also in other computational settings such as parallel computation
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ρ, 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, cache-oblivious procedure, and we believe
that it will be useful also in other computational settings such as parallel computation
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Algorithmica |
| Vol/bind | 78 |
| Udgave nummer | 4 |
| Sider (fra-til) | 1263-1283 |
| ISSN | 0178-4617 |
| DOI | |
| Status | Udgivet - 1 aug. 2017 |