# Distributed k-Means and k-Median Clustering on General Topologies

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2013.

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

- [Heterogeneity for the Win: One-Shot Federated Clustering](https://mlsanity.com/paper/2103.00697/) (2021)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [Secure Federated Clustering](https://mlsanity.com/paper/2205.15564/) (2022)
- [Differentially Private Federated Clustering over Non-IID Data](https://mlsanity.com/paper/2301.00955/) (2023)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [Correlation Aware Sparsified Mean Estimation Using Random Projection](https://mlsanity.com/paper/2310.18868/) (2023)
- [A Dynamic Mode Decomposition Approach for Decentralized Spectral Clustering of Graphs](https://mlsanity.com/paper/2203.00004/) (2022)
- [Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacy](https://mlsanity.com/paper/2303.00035/) (2023)
- [Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks](https://mlsanity.com/paper/2406.03766/) (2024)
- [Fast Distributed k-Means with a Small Number of Rounds](https://mlsanity.com/paper/2201.13217/) (2022)
- [Jigsaw Game: Federated Clustering](https://mlsanity.com/paper/2407.12764/) (2024)
- [Federated k-Means over Networks](https://mlsanity.com/paper/2510.09718/) (2025)
- [Communication-efficient k-Means for Edge-based Machine Learning](https://mlsanity.com/paper/2102.04282/) (2021)
- [An Accurate and Efficient Large-scale Regression Method through Best Friend Clustering](https://mlsanity.com/paper/2104.10819/) (2021)
- [Joint Coreset Construction and Quantization for Distributed Machine Learning](https://mlsanity.com/paper/2204.06652/) (2022)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [Distributed Clustering based on Distributional Kernel](https://mlsanity.com/paper/2409.09418/) (2024)
- [FedUHD: Unsupervised Federated Learning using In-Memory Hyperdimensional Computing](https://mlsanity.com/paper/2508.12021/) (2025)
- [Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs](https://mlsanity.com/paper/2601.17136/) (2026)
- [Distributed Gradient Clustering: Convergence and the Effect of Initialization](https://mlsanity.com/paper/2603.20507/) (2026)
- [Scalable and Distributed Silhouette Approximation](https://mlsanity.com/paper/2607.01993/) (2026)
- [CRHT: A Continuous Regression Hybrid Transformer for Vessel Trajectory Prediction with Online Cluster Sampling](https://mlsanity.com/paper/2608.10256/) (2026)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

This paper provides new algorithms for distributed clustering for two popular center-based objectives, k-median and k-means. These algorithms have provable guarantees and improve communication complexity over existing approaches. Following a classic approach in clustering by citehar2004coresets, we reduce the problem of finding a clustering with low cost to the problem of finding a coreset of small size. We provide a distributed method for constructing a global coreset which improves over the previous methods by reducing the communication complexity, and which works over general communication topologies. Experimental results on large scale data sets show that this approach outperforms other coreset-based distributed clustering algorithms.