I/O-Efficient Similarity Join
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
I/O-Efficient Similarity Join. / Pagh, Rasmus; Pham, Ninh; Silvestri, Francesco; Stöckel, Morten.
In: Algorithmica, Vol. 78, No. 4, 01.08.2017, p. 1263-1283.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - I/O-Efficient Similarity Join
AU - Pagh, Rasmus
AU - Pham, Ninh
AU - Silvestri, Francesco
AU - Stöckel, Morten
PY - 2017/8/1
Y1 - 2017/8/1
N2 - We present an I/O-efficient algorithm for computing similarity joins basedon locality-sensitive hashing (LSH). In contrast to the filtering methods commonlysuggested our method has provable sub-quadratic dependency on the data size. Further,in contrast to straightforward implementations of known LSH-based algorithms onexternal memory, our approach is able to take significant advantage of the availableinternal memory:Whereas the time complexity of classical algorithms includes a factorof Nρ, where ρ is a parameter of the LSH used, the I/O complexity of our algorithmmerely includes a factor (N/M)ρ, where N is the data size and M is the size ofinternal memory. Our algorithm is randomized and outputs the correct result withhigh probability. It is a simple, recursive, cache-oblivious procedure, and we believethat 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 basedon locality-sensitive hashing (LSH). In contrast to the filtering methods commonlysuggested our method has provable sub-quadratic dependency on the data size. Further,in contrast to straightforward implementations of known LSH-based algorithms onexternal memory, our approach is able to take significant advantage of the availableinternal memory:Whereas the time complexity of classical algorithms includes a factorof Nρ, where ρ is a parameter of the LSH used, the I/O complexity of our algorithmmerely includes a factor (N/M)ρ, where N is the data size and M is the size ofinternal memory. Our algorithm is randomized and outputs the correct result withhigh probability. It is a simple, recursive, cache-oblivious procedure, and we believethat it will be useful also in other computational settings such as parallel computation
U2 - 10.1007/s00453-017-0285-5
DO - 10.1007/s00453-017-0285-5
M3 - Journal article
VL - 78
SP - 1263
EP - 1283
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
IS - 4
ER -
ID: 194914537