This paper, presented as an extended abstract, introduces a more efficient way to perform similarity joins on massive datasets using parallel computing frameworks like MapReduce or Spark. By combining adaptive hashing techniques with parallel processing, the authors provide a theoretical framework that significantly reduces the communication overhead (the "load") when dealing with datasets that contain dense clusters of similar items.
TL;DR
The authors propose a constant-round MapReduce algorithm for similarity joins that adapts to the local density of data points. By leveraging multi-level Locality-Sensitive Hashing (LSH), the algorithm achieves better communication bounds than previous state-of-the-art parallel methods, particularly on structured datasets with dense clusters.
What Problem Does This Paper Address?
A similarity join is a fundamental database operation: given two sets of points, find all pairs that are "close" to each other (within a distance $r$). This is a massive computational challenge in high-dimensional spaces, often used for tasks like web deduplication, document clustering, and data cleaning.
While parallel frameworks like MapReduce help handle the scale, the primary bottleneck is often the communication load—the amount of data sent between processors. Previous parallel algorithms were "output-sensitive" (their speed depended on the number of results), but they didn't account for the internal structure of the data. For example, if a dataset has many dense clusters, standard algorithms might perform a lot of redundant work or generate too many "false positive" matches that must be filtered out, leading to high communication costs.
Methods
The paper builds on two major recent developments:
- Massively Parallel Similarity Joins (Hu et al., 2017): An algorithm designed for the MPC (Massively Parallel Computational) model that is sensitive to the total output size.
- Adaptive Sequential LSH (Ahle et al., 2017): A sequential algorithm that changes its hashing strategy based on the local density of points to minimize work.
The Innovation: The authors adapt the sequential "recursive stopping rule" into a parallel setting.
- Multi-level LSH: Instead of using a single hash function, the algorithm uses a hierarchy of hash functions with different lengths.
- Local Adaptivity: For every point in the dataset, the algorithm calculates an optimal "level" ($k_x$) for hashing. Points in dense regions are hashed differently than outliers to balance the cost of finding neighbors against the cost of processing "false positive" collisions.
- MPC Execution: The process is organized into $\kappa$ phases (where $\kappa$ is a small constant). Crucially, these phases can be run concurrently, maintaining a constant number of communication rounds ($O(1)$).
Datasets
Not discussed in the paper. As this is a theoretical "Extended Abstract," the authors focus on proving mathematical bounds for the algorithm's performance rather than providing empirical results on specific datasets. They do, however, mention that their techniques are applicable to various distance metrics, including Hamming, $\ell_1, \ell_2$, Jaccard, and Fréchet distance.
Key Insights and Ideas
- Density-Awareness is Key: Standard LSH treats every point the same. This paper recognizes that a "one size fits all" hashing strategy is inefficient for communication. By being "adaptive," the algorithm does less work for points in dense clusters.
- The "Aha" Moment: The authors show that you can determine the optimal hashing level for every point in parallel in just one round. This allows the adaptive strategy to work at scale without adding significant overhead.
- Smooth Performance Scaling: The algorithm matches the performance of previous best-in-class algorithms in the worst-case scenario (randomly distributed data) but provides a "smooth" increase in performance as the data becomes more structured and clustered.
Key Results
The results are expressed as theoretical bounds on the load ($L$), which represents the maximum number of messages any single processor has to send or receive.
- Improved Bounds: For a cluster of $\Omega(n)$ close points, the previous state-of-the-art load was $O(n/p^{1/(2(1+\rho))})$. This new algorithm improves that to $O(n/p^{1/2})$.
- Constant Rounds: The algorithm is guaranteed to finish in $O(1)$ rounds, which is the gold standard for MapReduce-style algorithms to avoid the latency of repeated synchronization.
- Parameter-Free: Unlike some specialized algorithms, this approach doesn't require the user to know the data's structure beforehand; it discovers and adapts to the density automatically.
Limitations and Future Work
- The $k_x$ Computation Term: The current bound includes a term ($n/p^{1/(1+\rho)}$) related to the initial step of calculating the optimal hash levels for each point. The authors acknowledge this might not be a tight bound and conjecture it can be reduced.
- Theoretical vs. Practical: While the math is promising, the authors note that an experimental evaluation is needed. They suggest that while their approach is theoretically sound for $O(1)$ rounds, some variations might require $O(\log n)$ rounds to achieve even better load balances.
- Approximation of $k_x$: Future work could involve using greedy approximations for collision probabilities to further speed up the initial setup phase of the algorithm.
Summary updated