Large Scale K-Clustering

Large-scale learning algorithms are essential for modern data collections that may have billions of data points. Here, we study the design of parallel \(k\) -clustering algorithms, which include the \(k\) -median, \(k\) -medoids, and \(k\) -means clustering problems. We design efficient parallel algorithms for these problems and prove that they still compute constant-factor approximations to the optimal solution for stable clustering instances. In addition to our theoretic results, we present computational experiments that show that our \(k\) -median and \(k\) -means algorithms work well in practice—we are able to find better clusterings than state-of-the-art coreset constructions using samples of the same size.