One-Shot Coresets: The Case of K-Clustering
Abstract
Scaling clustering algorithms to massive data sets is a challenging task. Recently, several successful approaches based on data summarization methods, such as coresets and sketches, were proposed. While these techniques provide provably good and small summaries, they are inherently problem dependent - the practitioner has to commit to a fixed clustering objective before even exploring the data. However, can one construct small data summaries for a wide range of clustering problems simultaneously? In this work, we affirmatively answer this question by proposing an efficient algorithm that constructs such one-shot summaries for k-clustering problems while retaining strong theoretical guarantees.
Cite
Text
Bachem et al. "One-Shot Coresets: The Case of K-Clustering." International Conference on Artificial Intelligence and Statistics, 2018.Markdown
[Bachem et al. "One-Shot Coresets: The Case of K-Clustering." International Conference on Artificial Intelligence and Statistics, 2018.](https://mlanthology.org/aistats/2018/bachem2018aistats-one/)BibTeX
@inproceedings{bachem2018aistats-one,
title = {{One-Shot Coresets: The Case of K-Clustering}},
author = {Bachem, Olivier and Lucic, Mario and Lattanzi, Silvio},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2018},
pages = {784-792},
url = {https://mlanthology.org/aistats/2018/bachem2018aistats-one/}
}