Distributed k-Means and k-Median Clustering on General Topologies
This work addresses efficient distributed clustering for large-scale data, though it appears incremental as it builds on prior coreset approaches.
The paper tackles distributed clustering for k-median and k-means by developing algorithms that reduce communication complexity and work over general topologies, with experimental results showing improved performance over existing coreset-based methods.
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.