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.