Fast Distributed k-Center Clustering with Outliers on Massive Data
Clustering large data is a fundamental problem with a vast number of applications. Due to the increasing size of data, practitioners interested in clustering have turned to distributed computation methods. In this work, we consider the widely used kcenter clustering problem and its variant used to handle noisy data, k-center with outliers. In the noise-free setting we demonstrate how a previously-proposed distributed method is actually an O(1)-approximation algorithm, which accurately explains its strong empirical performance. Additionally, in the noisy setting, we develop a novel distributed algorithm that is also an O(1)-approximation. These algorithms are highly parallel and lend themselves to virtually any distributed computing framework. We compare each empirically against the best known sequential clustering methods and show that both distributed algorithms are consistently close to their sequential versions. The algorithms are all one can hope for in distributed settings: they are fast, memory efficient and they match their sequential counterparts.
The 4-approximation is surprisingly simple: simply compute the k-center (approximately) in each machine, collect all such centers in a single machine, and then compute the k-center for these centers. The proof is also very simple. I am not sure if this simple argument has been found (or implied) from previous work. But if not, it is definitely a simple, yet nice and cute new result.The algorithm for the outlier version is somewhat harder. Again, compute the k-center (approximately) for the points in each machine, and collect all such centers in a single machine. Now, each such center can be through as a representative of several original points (by assigning a proper weight). Then the machine with all such centers runs an algorithm similar to Charikar et al. The analysis of the approximation ratio requires some effort. Overall, the results of the paper are nice. The theoretical depth is ok, yet not terribly deep nor exciting. I would rate it as a weak accept (7).Some minor comments:The idea of creating weighted point is somewhat similar to the recent work for a generalization of the outlier k-center problem. Chen, Danny Z., et al. "Matroid and knapsack center problems."Integer Programming and Combinatorial Optimization. Springer Berlin Heidelberg, 2013. 110-122. The work is in the very same spirit of several recent work on distributed and composable coreset, in which the idea is to compute a coreset on each machine, and then compute the approximate optimal solution for the union of all coresets. These papers are definitely related.Indyk, Piotr, et al. "Composable core-sets for diversity and coverage maximization."Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, 2014. Barbosa, Rafael, et al. "The Power of Randomization: Distributed Submodular Maximization on Massive Datasets."arXiv preprint arXiv:1502.02606 (2015).