# One-Shot Coresets: The Case of k-Clustering

arXiv: https://arxiv.org/abs/1711.09649 · HTML: https://mlsanity.com/paper/1711.09649/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2017.

## Built on by (most cited first, 15 of 15)

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Fair Wasserstein Coresets](https://mlsanity.com/paper/2311.05436/) (2023)
- [How to Use K-means for Big Data Clustering?](https://mlsanity.com/paper/2204.07485/) (2022)
- [Dataset Distillation Meets Provable Subset Selection](https://mlsanity.com/paper/2307.08086/) (2023)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)
- [Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithm](https://mlsanity.com/paper/2206.07852/) (2022)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [Clustering by Contour coreset and variational quantum eigensolver](https://mlsanity.com/paper/2312.03516/) (2023)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)
- [GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction](https://mlsanity.com/paper/2410.22347/) (2024)
- [A Generic Framework for Fair Consensus Clustering in Streams](https://mlsanity.com/paper/2602.11500/) (2026)
- [Data-Native Global Optimization for Big Data K-means Clustering](https://mlsanity.com/paper/2607.15835/) (2026)

## Abstract (arXiv)

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.