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

Source: [Distributed k-Means and k-Median Clustering on General Topologies](<https://www.sota2.com/research/paper/68fa67001e209131cea13a25>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T22:03:19.943Z

Authors: Maria Florina Balcan, Steven Ehrlich, Yingyu Liang

Published: 2013-06-03T21:49:19.000Z

## Abstract

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 \\cite{har2004coresets}, 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [k-means clustering on YearPredictionMSD (train)](<https://www.sota2.com/research/sota/k-means-clustering-on-yearpredictionmsd-train.md>): k-means clustering; YearPredictionMSD (train); Avg Cost: 74.89.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1306.0604>)

[PDF](<https://arxiv.org/pdf/1306.0604.pdf>)