mlsanityData to 7 Oct 2026

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

arXiv 1306.0604 ↗First posted 3 Jun 2013cs.LG cs.DC stat.MLcited by 24

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 5; 2024: 4; 2025: 2; 2026: 5.

24 papers.

Sort:

  1. 2021Heterogeneity for the Win: One-Shot Federated Clusteringcited by 87
  2. 2022Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clusteringcited by 14
  3. 2022Secure Federated Clusteringcited by 10
  4. 2023Differentially Private Federated Clustering over Non-IID Datacited by 7
  5. 2023Dataset Distillation Meets Provable Subset Selectioncited by 7
  6. 2023AutoCoreset: An Automatic Practical Coreset Construction Frameworkcited by 4
  7. 2023Correlation Aware Sparsified Mean Estimation Using Random Projectioncited by 3
  8. 2022A Dynamic Mode Decomposition Approach for Decentralized Spectral Clustering of Graphscited by 2
  9. 2023Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacycited by 2
  10. 2024Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networkscited by 2
  11. 2022Fast Distributed k-Means with a Small Number of Roundscited by 1
  12. 2024Jigsaw Game: Federated Clusteringcited by 1
12 more
  1. 2025Federated k-Means over Networkscited by 1
  2. 2021Communication-efficient k-Means for Edge-based Machine Learningcited by 0
  3. 2021An Accurate and Efficient Large-scale Regression Method through Best Friend Clusteringcited by 0
  4. 2022Joint Coreset Construction and Quantization for Distributed Machine Learningcited by 0
  5. 2024A Unified Framework for Center-based Clustering of Distributed Datacited by 0
  6. 2024Distributed Clustering based on Distributional Kernelcited by 0
  7. 2025FedUHD: Unsupervised Federated Learning using In-Memory Hyperdimensional Computingcited by 0
  8. 2026Communication-Avoiding Linear Algebraic Kernel K-Means on GPUscited by 0
  9. 2026Distributed Gradient Clustering: Convergence and the Effect of Initializationcited by 0
  10. 2026Scalable and Distributed Silhouette Approximationcited by 0
  11. 2026CRHT: A Continuous Regression Hybrid Transformer for Vessel Trajectory Prediction with Online Cluster Samplingcited by 0
  12. 2026Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Samplingcited by 0