Distributed $k$-means and $k$-median Clustering on General Topologies

Maria-Florina F Balcan, Steven Ehrlich, Yingyu Liang

Advances in Neural Information Processing Systems 26 (NIPS 2013)

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. We provide experimental evidence for this approach on both synthetic and real data sets.