Abstract
Large-scale clustering of data points in metric spaces is an important problem in mining big data sets. For many applications, we face explicit or implicit size constraints for each cluster which leads to the problem of clustering under capacity constraints or the "balanced clustering" problem. Although the balanced clustering problem has been widely studied, developing a theoretically sound distributed algorithm remains an open problem. In the present paper we develop a general framework based on "mapping coresets" to tackle this issue. For a wide range of clustering objective functions such as k-center, k-median, and k-means, our techniques give distributed algorithms for balanced clustering that match the best known single machine approximation ratios.
Introduction
Clustering is a fundamental tool for organizing large-scale data. However, in many real-world applications, clusters cannot be of arbitrary size. For instance, when assigning data points to machines for processing, each machine has a hard storage limit. This necessitates balanced clustering (or capacitated clustering).
While standard clustering is well-understood, adding balance constraints significantly increases complexity. In distributed environments, this difficulty is amplified by the need to ensure cluster size limits without constant, expensive communication. Prior to this work, distributed algorithms for balanced clustering lacked "approximation guarantees"—mathematical proofs that the solution found is within a bounded factor of the optimal solution.
Methods: Mapping Coresets
The authors introduce a new framework based on Mapping Coresets. A standard coreset is a small subset of points representing the geometry of the entire set. A mapping coreset adds a mathematical function that maps every original point to a specific point in the coreset, preserving assignment information.
These coresets are "composable," allowing for a parallelized workflow:
- Partition: Split data across multiple machines.
- Summarize: Each machine computes a mapping coreset independently and assigns weights (multiplicities) to points.
- Reduce: Send these small summaries to a single machine.
- Solve: Run a space-efficient sequential algorithm on the combined summary.
- Map Back: Use the stored mapping functions to translate the summary's clusters back to the original dataset.
Key Results
Theoretical Guarantees
The paper establishes the first constant-factor approximation for distributed balanced $k$-center and $O(p)$ for $k$-clustering in $\ell_p$ metrics. These results apply to both MapReduce and streaming models, typically requiring only a constant number of rounds or passes.
Empirical Scalability and Quality
The approach was evaluated using large-scale geographic datasets, including the US Road Network (tens of millions of nodes) and a World Graph (hundreds of millions of nodes).
- Efficiency: On the World Graph, the algorithm demonstrated sublinear scaling; a ten-fold increase in data size resulted in only a 3.6x increase in running time.
- Quality Preservation: Compared to a sequential heuristic on a small sample, the distributed approach maintained high solution quality, with cluster radius degradation limited to approximately 50-60%.
Conclusion and Future Work
While the framework provides strong theoretical foundations, the approximation constants are currently somewhat pessimistic compared to real-world performance. Future work may focus on closing this gap and extending the framework to non-metric or high-dimensional spaces where the triangle inequality does not hold. Additionally, achieving constant factor approximations for $k$-median and $k$-means without allowing for bicriteria relaxations (like opening $2k$ centers) remains a significant theoretical challenge.
Summary updated