Distributed Balanced Clustering via Mapping Coresets.

MohammadHossein Bateni, Aditya Bhaskara, Silvio Lattanzi, Vahab S. MirrokniNeurIPS 2014 · OpenReview

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.

The Mapping Coreset Workflow: from partitioning to final assignment.

These coresets are "composable," allowing for a parallelized workflow:

  1. Partition: Split data across multiple machines.
  2. Summarize: Each machine computes a mapping coreset independently and assigns weights (multiplicities) to points.
  3. Reduce: Send these small summaries to a single machine.
  4. Solve: Run a space-efficient sequential algorithm on the combined summary.
  5. 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.

Theoretical approximation ratios and complexity for various clustering problems.

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

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 <code>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</code>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.
BibTeX
@inproceedings{bateni2014distributed,
  author = {MohammadHossein Bateni and Aditya Bhaskara and Silvio Lattanzi and Vahab S. Mirrokni},
  title = {{Distributed Balanced Clustering via Mapping Coresets.}},
  booktitle = {NeurIPS},
  year = {2014},
  url = {https://openreview.net/forum?id=XsNBqqtNjhI},
}
Figure