TY - JOUR
T1 - I/O-efficient Similarity Join
AU - Pagh, Rasmus
AU - Pham, Ninh Dang
AU - Silvestri, Francesco
AU - Stöckel, Morten Danmark
PY - 2017
Y1 - 2017
N2 - 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 subquadratic 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.
AB - 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 subquadratic 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.
U2 - 10.48550/arXiv.1507.00552
DO - 10.48550/arXiv.1507.00552
M3 - Journal article
SN - 0178-4617
VL - 78
JO - Algorithmica
JF - Algorithmica
ER -