Efficient parallel set-similarity joins using MapReduce

TLDR

The paper proposes a 3‑stage MapReduce framework to perform set‑similarity joins efficiently in parallel. The approach partitions data across nodes to balance load and reduce replication, handles both self‑join and R‑S join cases, controls memory usage, and includes strategies for when data exceeds node memory. Experiments on real and synthetically enlarged datasets in Hadoop demonstrate significant speedup and scaleup of the proposed algorithms.

Abstract

In this paper we study how to efficiently perform set-similarity joins in parallel using the popular MapReduce framework. We propose a 3-stage approach for end-to-end set-similarity joins. We take as input a set of records and output a set of joined records based on a set-similarity condition. We efficiently partition the data across nodes in order to balance the workload and minimize the need for replication. We study both self-join and R-S join cases, and show how to carefully control the amount of data kept in main memory on each node. We also propose solutions for the case where, even if we use the most fine-grained partitioning, the data still does not fit in the main memory of a node. We report results from extensive experiments on real datasets, synthetically increased in size, to evaluate the speedup and scaleup properties of the proposed algorithms using Hadoop.