TL;DR
This paper introduces two highly efficient, two-round MapReduce algorithms for $k$-center clustering: one for standard datasets and a novel variant for datasets containing outliers. Both algorithms provide constant-factor approximation guarantees and achieve massive speedups—up to 677x—while maintaining clustering quality nearly identical to their sequential counterparts.
The Challenge of Scale and Noise in Clustering
Clustering is a cornerstone of machine learning, used for everything from document grouping to targeted advertising. The $k$-center problem specifically aims to find $k$ points (centers) such that the maximum distance from any data point to its nearest center is minimized.
However, modern practitioners face two major hurdles:
- Scale: As datasets grow to millions or billions of points, sequential algorithms become too slow and exceed the memory limits of a single machine.
- Noise: Standard $k$-center clustering is extremely sensitive to outliers. A single noisy point far from the rest of the data can "pull" a center away from a dense cluster, ruining the result.
While distributed frameworks like MapReduce are the standard for "Big Data," existing distributed $k$-center algorithms often lack theoretical guarantees or perform poorly when data is missing due to sampling. This paper fills that gap by providing distributed algorithms that are both theoretically sound and practically fast.
A Two-Round MapReduce Approach
The authors propose two primary algorithms designed for the MapReduce framework, which operates in discrete "rounds" of parallel computation and data shuffling.
GREEDY-MR (For Standard $k$-Center)
- Round 1: Data is partitioned across $m$ machines. Each machine independently runs a sequential greedy algorithm to find $k$ local centers.
- Round 2: All local centers (totaling $m \times k$ points) are sent to a single machine, which runs the greedy algorithm again to select the final $k$ global centers.
- The Innovation: The authors prove this simple approach is a 4-approximation algorithm, providing a theoretical explanation for why this intuitive method works so well in practice.
OUTLIERS-MR (For $k$-Center with Outliers)
Handling outliers is significantly harder because the algorithm must decide which $z$ points to ignore while simultaneously picking centers. This is the paper's most significant contribution.
- Round 1: Each machine finds $k+z$ local centers. Crucially, it also calculates a weight for each center, representing how many original data points that center "covers."
- Round 2: These weighted "proxy" points are sent to a central machine. The authors developed a new
CLUSTERsubroutine that uses these weights to distinguish between dense clusters and sparse outliers. - The Innovation: They prove this achieves an O(1)-approximation (specifically a 13-approximation), marking the first such result for distributed $k$-center with outliers.
Key Insights
- Weighted Proxies are Powerful: Instead of sending all data to one machine (which is impossible) or relying on random samples (which is inaccurate), sending a small set of weighted centers acts as a highly effective "summary" of the data distribution.
- The "Guessing" Strategy: The outlier algorithm relies on a parameter $G$, which is a "guess" of the optimal radius. By performing a parallel binary search for $G$, the algorithm can find the optimal clustering threshold efficiently.
Key Results
The authors evaluated their methods on seven diverse real-world datasets, ranging from small biomedical datasets to an 11-million-point physics dataset (Higgs).
- Quality Preservation: As shown in the results above, the distributed versions (
GREEDY-MRandOUTLIERS-MR) produced objective values nearly identical to the sequential versions across varying numbers of clusters, outliers, and machines. They also significantly outperformed "naive" distributed baselines like random sampling. - Massive Speedups: On the Census dataset, the distributed outlier algorithm was 677x faster than the sequential version. This is largely because the distributed version avoids the need to compute a massive, memory-intensive distance matrix.
- Extreme Scalability: The
OUTLIERS-MRalgorithm successfully clustered the 11-million-point Higgs dataset in less than 15 minutes, a task that would be computationally prohibitive for standard sequential approaches.
Limitations and Future Work
While the theoretical bound for the outlier algorithm is a 13-approximation—a breakthrough for distributed outlier clustering—it is theoretically "looser" than the sequential 3-approximation. Future work could aim to tighten this bound.
Additionally, the algorithm requires the number of outliers $z$ to be specified upfront. In some real-world scenarios, $z$ might be unknown, requiring further heuristics to estimate. However, the authors suggest that the "weighted proxy" approach used here could potentially be adapted for other clustering objectives, such as $k$-median or $k$-means with outliers, opening exciting new avenues for distributed machine learning.
Summary updated