Distributed Balanced Clustering via Mapping Coresets
Large-scale clustering 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 clustering under capacity constraints or the "balanced clustering" problem. Although the balanced clustering 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 clustering problems for a wide range of clustering objective functions such as k-center, k-median, and k-means.
The paper describes an approach to distributed (balanced) clustering using the notion of a coreset, a concept introduced and studied in theoretical computer science in the areas of approximation algorithms and computational geometry. Starting from a recent work of Indyk et al. (PODS’14) the authors introduce the idea of “mapping coresets” which is basically a coreset together with a mapping from the the original space to the coreset points. Basically the proposed clustering algorithm works as follows: first the input data set is partitioned into several chunks arbitrarily. Then, for each chunk, a coreset is computed together with a mapping of the original points in the chunk to those in the coreset. Next, clustering is performed over the union of all the coresets and the solution found is finally mapped back to the original data points. After a long list of definitions the authors provide some theoretical properties and show connections to MapReduce and streaming clustering algorithms.The writing of the paper is quite dense and technical, and it is not easy to read. Also, the authors presuppose familiarity with coresets and its properties and with results from  approximation algorithms. Indeed, almost all references come basically from the theoretical computer science area (STOC, FOCS, SODA, etc.).All in all the contribution is quite incremental. The idea of using coresets in distributed clustering has been used before extensively, although the idea introduced here of mapping coresets and the application to balanced clustering looks novel. The connection with MapReduce and streaming clustering algorithm is interesting but I'm not sure this will appeal to the NIPS community.A major weakness of the paper, however, is the experimental evaluation which aimed to show the scalability of the proposed algorithm. Indeed, the authors applied their implementation of the algorithm on just two (admittedly very large) graphs, so the overall conclusions are questionable.