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

Research output: Journal Article or Conference Article in Journal › Journal article › Research › 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:

Original language	English
Journal	Algorithmica
Volume	78
ISSN	0178-4617
DOIs	https://doi.org/10.48550/arXiv.1507.00552
Publication status	Published - 2017

Keywords

cache oblivious
cache aware
locality sensitive hashing
Similarity join

Access to Document

10.48550/arXiv.1507.00552

https://arxiv.org/pdf/1507.00552.pdfLicence: Other

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

Cite this

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

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

Keywords

Access to Document

Fingerprint

Projects

SSS: Scalable Similarity Search

Cite this