Adaptive MapReduce Similarity Joins

Samuel McCauley, Francesco Silvestri

Abstract

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 \in S$ and $y \in 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 size 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.

Introduction

A similarity join is a core operation in modern data processing, used for tasks ranging from web deduplication and document clustering to data cleaning. Formally, given two sets of points, the objective is to identify all pairs within a specified distance $r$. In high-dimensional spaces, this task becomes computationally expensive. While parallel frameworks like MapReduce and Spark provide the necessary scale, they introduce a new bottleneck: communication load.

The communication load ($L$)—the maximum amount of data any single processor must send or receive—often determines the overall runtime of the algorithm. Previous state-of-the-art parallel algorithms were "output-sensitive," meaning their performance scaled with the number of results. However, these methods failed to account for the internal structure of the data, such as dense clusters, which can lead to redundant work and excessive "false positive" matches.

Methodology

This research bridges the gap between output-sensitive parallel joins and density-aware sequential hashing. The proposed algorithm adapts the "recursive stopping rule" from sequential LSH into the Massively Parallel Computational (MPC) model.

Multi-level LSH and Local Adaptivity

Instead of applying a uniform hash function to all data points, the algorithm utilizes a hierarchy of hash functions with varying lengths. For every point $x$ in the dataset, the algorithm calculates an optimal hashing level, denoted as $k_x$.

This local adaptivity is crucial: points residing in dense regions are hashed differently than isolated outliers. By adjusting the hashing level based on local density, the algorithm balances the cost of identifying true neighbors against the cost of processing collisions from false positives.

Parallel Execution in the MPC Model

A key challenge in adaptive algorithms is preventing the adaptation process itself from becoming a bottleneck. The authors demonstrate that the optimal $k_x$ for every point can be determined in parallel within a single round. The overall execution is organized into $\kappa$ phases (where $\kappa$ is a small constant). These phases are designed to run concurrently, ensuring the algorithm maintains a constant number of communication rounds ($O(1)$), which is the gold standard for minimizing synchronization latency in MapReduce environments.

Theoretical Results

The primary contribution of this work is the improvement of theoretical communication bounds. The algorithm is "parameter-free" in the sense that it does not require prior knowledge of the data's distribution; it discovers and adapts to the density automatically.

  • Load Efficiency: In scenarios involving a cluster of $\Omega(n)$ close points, previous algorithms achieved a load of $O(n/p^{1/(2(1+\rho))})$. The new adaptive approach improves this bound to $O(n/p^{1/2})$.
  • Worst-Case Robustness: While the algorithm excels on structured data, it matches the performance of existing best-in-class algorithms in the worst-case scenario (e.g., randomly distributed data).
  • Round Complexity: The algorithm guarantees completion in $O(1)$ rounds, making it highly suitable for practical parallel systems.

Discussion and Future Work

While the theoretical bounds are a significant step forward, the authors identify areas for further refinement. The current bound includes a term ($n/p^{1/(1+\rho)}$) associated with the initial calculation of $k_x$. There is a conjecture that this term can be further reduced to provide even tighter bounds.

Additionally, while the mathematical framework is robust, empirical evaluation is the next logical step. The authors suggest that while $O(1)$ rounds are theoretically sufficient, certain variations of the algorithm might benefit from $O(\log n)$ rounds to achieve even more precise load balancing in practical deployments. Future research may also explore greedy approximations for collision probabilities to streamline the initial setup phase.

Summary updated

Abstract

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 in S and y in 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\"uller, 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.
BibTeX
@inproceedings{mccauley2018adaptive,
  author = {Samuel McCauley and Francesco Silvestri},
  title = {{Adaptive MapReduce Similarity Joins}},
  booktitle = {BeyondMR@SIGMOD},
  year = {2018},
  url = {https://openreview.net/forum?id=LL7H4uJB1N},
}
Figure