TL;DR
This paper introduces the first distributed, parallel algorithm for the Euclidean hierarchical $k$-median clustering problem that comes with rigorous theoretical guarantees. By cleverly embedding data into a specialized tree structure and decoupling the dependencies of a greedy algorithm, the authors achieve massive empirical speedups (up to 300x faster than existing baselines) while maintaining a strict, low-memory footprint per machine.
What Problem Does This Paper Address?
Clustering is a foundational tool in unsupervised machine learning, and hierarchical clustering is particularly valuable because it captures the nested structures of real-world data. The Euclidean hierarchical $k$-median problem asks us to find a sequence of cluster centers and nested partitions that minimize the $k$-median cost for all possible values of $k$ (from 1 to $n$).
While there are distributed algorithms for "flat" $k$-median clustering, they typically require memory per machine that scales with $k$ (e.g., $O(k + n^\epsilon)$). This is a dealbreaker for hierarchical clustering, where we need to compute solutions for all $k$, up to $k = n-1$. Recent attempts at parallel hierarchical clustering either lacked theoretical guarantees on the quality of their output or required too many sequential rounds of communication. This paper bridges that gap by designing an algorithm in the Massive Parallel Computation (MPC) model that uses extremely small memory per machine while guaranteeing a bounded approximation error.
Methods
The authors' approach elegantly combines metric embeddings with a highly parallelizable greedy strategy:
- Tree Embedding: The algorithm first embeds the $d$-dimensional Euclidean dataset into a 2-Restricted Hierarchically Well-Separated Tree (2-RHST) using a random quad-tree embedding. This step maps the complex spatial relationships into a simpler tree metric, incurring a small, bounded distortion in distances.
- Optimal Greedy on Trees: The authors prove that a simple greedy algorithm—iteratively picking the center that reduces the clustering cost the most—is actually optimal for the $k$-median problem on a 2-RHST.
- Decoupling Dependencies for Parallelization: A standard greedy algorithm is inherently sequential (choice $i$ depends on choices $1$ through $i-1$). The authors' crucial innovation is showing that in a 2-RHST, the "benefit" of opening a new center at a specific tree level can be precomputed independently of the exact configuration of previously chosen centers.
- MPC Implementation: Because the benefits can be precomputed, the sequential greedy algorithm is transformed into a highly parallelizable process of computing local sums, finding maximums, and sorting. This fits perfectly into the MPC model, requiring only a few rounds of communication.
Datasets
The authors evaluated their algorithm on several standard, large-scale datasets from the UCI Machine Learning Repository:
- KDD Cup (Intrusion): $n \approx 31$K, $d = 35$
- YearPredictionMSD (SONG): $n \approx 515$K, $d = 90$
- US Census Data (1990): $n \approx 2.45$M, $d = 29$
- HIGGS: $n = 11$M, $d = 28$
To test the limits of their algorithm's scalability, they also artificially expanded the HIGGS dataset to create massive benchmarks of up to 10 billion points.
Key Insights and Ideas
- The "Aha!" Moment of Tree Metrics: The most brilliant insight is that in a 2-RHST, the distance from a point to its nearest center depends only on the tree level where their paths diverge. This structural quirk is what allows the algorithm to precalculate the benefit of opening a center without knowing the full state of the clustering.
- Sub-linear Memory: By reducing the problem to sorting and filtering precomputed values, the algorithm requires memory per machine of only $s \in \Omega(\log^2(n + \Delta + d))$ (where $\Delta$ is the ratio of the max to min distance between points). This entirely bypasses the traditional $O(k)$ memory bottleneck.
- Almost Optimal Work Efficiency: The total computational work done across all machines is $O(nd)$, meaning the algorithm is almost linear in the size of the input.
Key Results
- Theoretical Guarantees: The algorithm guarantees an expected approximation factor of $O(\min\{d, \log n\} \log \Delta)$ for any fixed $k$, and $O(\min\{d, \log n\} \log \Delta \log(\Delta dn))$ simultaneously for all $k$. It runs in a constant number of rounds if the memory per machine is $n^\delta$.
- Hierarchical Speedups: In distributed settings, the algorithm outperforms the state-of-the-art parallel hierarchical baseline (LLLM) by 2-3% in clustering quality while being 10x to 26x faster, depending on the dataset and cluster size.
- Flat Clustering Dominance: When used just for flat $k$-median clustering at large $k$ (e.g., $k=10,000$), the algorithm is staggeringly fast. On the Census dataset, it is 40x faster than $k$-median++, 41x faster than BEL, and 300x faster than PLSH.
Limitations and Future Work
- Limitations: The theoretical approximation factor relies heavily on the initial tree embedding, which introduces an $O(d \log \Delta)$ distortion. Additionally, the core theoretical guarantee holds in expectation for a fixed $k$, rather than as a strict worst-case bound.
- Future Work: The authors suggest that their core technique (decoupling greedy choices on a tree) could be extended to general $k$-clustering problems, including $k$-means and higher powers. The main hurdle for future research is finding better, lower-distortion RHST constructions that can be computed in a constant number of MPC rounds.
Summary updated