# Fast Distributed k-Means with a Small Number of Rounds

arXiv: https://arxiv.org/abs/2201.13217 · HTML: https://mlsanity.com/paper/2201.13217/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 30 references that are in the map.
- First posted on arXiv 31 Jan 2022.

## Builds on (most cited first, 11 of 11)

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Robust Federated Learning in a Heterogeneous Environment](https://mlsanity.com/paper/1906.06629/) (2019)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [MLlib: Machine Learning in Apache Spark](https://mlsanity.com/paper/1505.06807/) (2015)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Distributed k-Means and k-Median Clustering on General Topologies](https://mlsanity.com/paper/1306.0604/) (2013)
- [A Practical Algorithm for Distributed Clustering and Outlier Detection](https://mlsanity.com/paper/1805.09495/) (2018)
- [Distributed k-Clustering for Data with Heavy Noise](https://mlsanity.com/paper/1810.07852/) (2018)
- [Communication-Optimal Distributed Clustering](https://mlsanity.com/paper/1702.00196/) (2017)
- [Distributed Partial Clustering](https://mlsanity.com/paper/1703.01539/) (2017)
- [A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering](https://mlsanity.com/paper/2102.04050/) (2021)

## Built on by (most cited first, 1 of 1)

- [Jigsaw Game: Federated Clustering](https://mlsanity.com/paper/2407.12764/) (2024)

## Abstract (arXiv)

We propose a new algorithm for k-means clustering in a distributed setting, where the data is distributed across many machines, and a coordinator communicates with these machines to calculate the output clustering. Our algorithm guarantees a cost approximation factor and a number of communication rounds that depend only on the computational capacity of the coordinator. Moreover, the algorithm includes a built-in stopping mechanism, which allows it to use fewer communication rounds whenever possible. We show both theoretically and empirically that in many natural cases, indeed 1-4 rounds suffice. In comparison with the popular k-means|| algorithm, our approach allows exploiting a larger coordinator capacity to obtain a smaller number of rounds. Our experiments show that the k-means cost obtained by the proposed algorithm is usually better than the cost obtained by k-means||, even when the latter is allowed a larger number of rounds. Moreover, the machine running time in our approach is considerably smaller than that of k-means||. Code for running the algorithm and experiments is available at https://github.com/selotape/distributed_k_means.