Google Research

Scalable k-Means Clustering via Lightweight Coresets

International Conference on Knowledge Discovery and Data Mining (KDD) (2018)

Abstract

Coresets are compact representations of datasets such that models trained on a coreset are provably competitive with models trained on the full data set. As such, they have been successfully used to scale up clustering models to massive data sets. While existing approaches generally only allow for multiplicative approximation errors, we propose a novel notion of lightweight coresets that allows for both multiplicative and additive errors. We provide a single algorithm to construct lightweight coresets for k-Means clustering as well as soft and hard Bregman clustering. The algorithm is substantially faster than existing constructions, embarrassingly parallel and the resulting coresets are smaller. We demonstrate that the proposed method outperforms existing coreset constructions in practice.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work