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

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.

Corrected Theorem 4 in the appendix

Cited by in corpus (10)

• Making AI Forget You: Data Deletion in Machine Learning
• Greedy Column Subset Selection: New Bounds and Distributed Algorithms
• Training Gaussian Mixture Models at Scale via Coresets
• Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures
• Tradeoffs for Space, Time, Data and Risk in Unsupervised Learning
• Sliding Window Algorithms for k-Clustering Problems
• Clustering with Distributed Data
• Optimal Bounds on the VC-dimension
• k-variates++: more pluses in the k-means++
• Robust Coreset Construction for Distributed Machine Learning