Distributed k-Means and k-Median Clustering on General Topologies
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 [13], 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.
This paper proposes new distributed algorithms for 
      k-means and k-median methods. Its main idea is to construct a global 
      coreset in a distributed fashion using cost information from local 
      approximations. This paper is well written with solid content. It proposes 
      distributed protocol for k-means/median clustering based on coreset 
      construction, provides theoretical guarantee on the approximation and 
      upper bounds on the communication cost, performs a couple of experiments 
      to show the proposed approach outperforms the existing ones. 
      Having said, the paper also comes with several caveats. First of 
      all, it is not very clear what is the main technical contribution of the 
      paper, especially given the existing works in [5], [10] and [19]. Using 
      coreset idea for approximating clustering algorithms is well studied 
      (e.g., in [5],[10]), and a distributed clustering algorithm based on 
      coreset is proposed in [19]. I clearly see that this paper contributes a 
      distributed method for constructing coreset independent of the network 
      topology, and develops a better algorithm than that in [19], by reducing 
      the communication cost by a factor of sqrt(n). However, the distributed 
      coreset construction in Algorithm 1 and the related bounds seems to be a 
      straightforward application of results in [5]. It is nice to see 
      the theoretical analysis on the algorithm and the upper bounds on coreset 
      size and communication cost. However, the upper bounds seem to be too 
      loose to use in practical applications. Given a dataset and its location 
      over a distributed network, how could you determine the size of coreset? 
      The bound for achieving this goal for k-means is along the line of 
      O(kd/(e^4)), which could be huge even for moderate large k, d and relative 
      small e. For example, for k=10, d = 100, e = 0.1, the size of coreset 
      predicted by your bound is 10 million, which could be way more larger than 
      the actual data size. In the experiments, the number of 
      distributed sites is small (e.g., 10 for Pendigits, 25 for 
      ColorHistogram). Have you tried experiments with larger number of 
      distributed sites? In addition, the three datasets used are relative-low 
      dimensional. Would this kind of approach work for high-dimensional sparse 
      data?