mlsanityData to 7 Oct 2026

One-Shot Coresets: The Case of k-Clustering

arXiv 1711.09649 ↗First posted 27 Nov 2017stat.ML cs.LGcited by 15

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 6; 2023: 5; 2024: 1; 2025: 0; 2026: 2.

15 papers.

Sort:

  1. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  2. 2022Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptionscited by 20
  3. 2023Fair Wasserstein Coresetscited by 8
  4. 2022How to Use K-means for Big Data Clustering?cited by 7
  5. 2023Dataset Distillation Meets Provable Subset Selectioncited by 7
  6. 2022Coresets for Data Discretization and Sine Wave Fittingcited by 6
  7. 2022Obstacle Aware Sampling for Path Planningcited by 6
  8. 2021Introduction to Coresets: Approximated Meancited by 5
  9. 2022Performance analysis of coreset selection for quantum implementation of K-Means clustering algorithmcited by 5
  10. 2023AutoCoreset: An Automatic Practical Coreset Construction Frameworkcited by 4
  11. 2023Clustering by Contour coreset and variational quantum eigensolvercited by 2
  12. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
3 more
  1. 2024GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reductioncited by 0
  2. 2026A Generic Framework for Fair Consensus Clustering in Streamscited by 0
  3. 2026Data-Native Global Optimization for Big Data K-means Clusteringcited by 0