Distributed Balanced Clustering via Mapping Coresets

Abstract

Large-scale of data points in metric spaces is an important problem in mining big data sets. For many applications, we face explicit or implicit size constraints for each cluster which leads to the problem of under capacity constraints or the clustering problem. Although the balanced problem has been widely studied, developing a theoretically sound distributed algorithm remains an open problem. In this paper we develop a new framework based on mapping coresets to tackle this issue. Our technique results in first distributed approximation algorithms for balanced problems for a wide range of objective functions such as k-center, k-median, and k-means.