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

Københavns Universitet

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

Emneord

cache oblivious
cache aware
locality sensitive hashing
Similarity join

Adgang til dokumentet

10.48550/arXiv.1507.00552

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

SSS: Scalable Similarity Search
Pagh, R. (PI), Christiani, T. L. (CoI), Pham, N. D. (CoI), Faithfull, A. (CoI), Silvestri, F. (CoI), Mikkelsen, J. W. (CoI), Sivertsen, J. V. T. (CoI), Aumüller, M. (CoI), Skala, M. (CoI), Ceccarello, M. (CoI), Themsen, R. (CoI), Jacob, R. (CoI), McCauley, S. (CoI) & Ahle, T. D. (CoI)
European Commission
01/05/2014 → 30/04/2019
Projekter: Projekt › Forskning

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

}

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

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

Emneord

Adgang til dokumentet

Fingeraftryk

Projekter

SSS: Scalable Similarity Search

Citationsformater