Adaptive MapReduce Similarity Joins

Samuel McCauley, Francesco Silvestri

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Similarity joins are a fundamental database operation. Given data sets S and R, the goal of a similarity join is to find all points x ∈ S and y ∈ R with distance at most r. Recent research has investigated how locality-sensitive hashing (LSH) can be used for similarity join, and in particular two recent lines of work have made exciting progress on LSH-based join performance. Hu, Tao, and Yi (PODS 17) investigated joins in a massively parallel setting, showing strong results that adapt to the size of the output. Meanwhile, Ahle, Aumüller, and Pagh (SODA 17) showed a sequential algorithm that adapts to the structure of the data, matching classic bounds in the worst case but improving them significantly on more structured data.

We show that this adaptive strategy can be adapted to the parallel setting, combining the advantages of these approaches. In particular, we show that a simple modification to Hu et al.'s algorithm achieves bounds that depend on the density of points in the dataset as well as the total outsize of the output. Our algorithm uses no extra parameters over other LSH approaches (in particular, its execution does not depend on the structure of the dataset), and is likely to be efficient in practice.
Original languageEnglish
Title of host publicationProceedings of the 5th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond : BeyondMR'18
PublisherAssociation for Computing Machinery
Publication date2018
ISBN (Print)978-1-4503-5703-6
Publication statusPublished - 2018


Dive into the research topics of 'Adaptive MapReduce Similarity Joins'. Together they form a unique fingerprint.

Cite this