I/O-efficient Similarity Join

Rasmus Pagh; Ninh Dang Pham; Francesco Silvestri; Morten Danmark Stöckel

doi:10.48550/arXiv.1507.00552

I/O-efficient Similarity Join

Rasmus Pagh, Ninh Dang Pham, Francesco Silvestri, Morten Danmark Stöckel

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

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 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:

Originalsprog	Engelsk
Tidsskrift	Algorithmica
Vol/bind	78
ISSN	0178-4617
DOI	https://doi.org/10.48550/arXiv.1507.00552
Status	Udgivet - 2017

Adgang til dokumentet

10.48550/arXiv.1507.00552

https://arxiv.org/pdf/1507.00552.pdfLicens: Andet

Citationsformater

@article{5c4a3be9fff8424d9a318e10d7a5aad0,

title = "I/O-efficient Similarity Join",

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 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: ",

keywords = "cache oblivious, cache aware, locality sensitive hashing, Similarity join",

author = "Rasmus Pagh and Pham, {Ninh Dang} and Francesco Silvestri and St{\"o}ckel, {Morten Danmark}",

year = "2017",

doi = "10.48550/arXiv.1507.00552",

language = "English",

volume = "78",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York LLC",

}

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:

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:

KW - cache oblivious

KW - cache aware

KW - locality sensitive hashing

KW - Similarity join

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 -

I/O-efficient Similarity Join

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater