mlsanityData to 14 Oct 2026

An Empirical Evaluation of k-Means Coresets

arXiv 2207.00966 ↗First posted 3 Jul 2022cs.DS cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

Coresets are among the most popular paradigms for summarizing data. In particular, there exist many high performance coresets for clustering problems such as k-means in both theory and practice. Curiously, there exists no work on comparing the quality of available k-means coresets. In this paper we perform such an evaluation. There currently is no algorithm known to measure the distortion of a candidate coreset. We provide some evidence as to why this might be computationally difficult. To complement this, we propose a benchmark for which we argue that computing coresets is challenging and which also allows us an easy (heuristic) evaluation of coresets. Using this benchmark and real-world data sets, we conduct an exhaustive evaluation of the most commonly used coreset algorithms from theory and practice.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 23 of its 51 references that are in the map. First posted on arXiv 3 Jul 2022.

Builds on

23 of 51 references.

References · 23

  1. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  2. 2018On Coresets for Logistic Regressioncited by 67
  3. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  4. 2019Coresets for Clustering with Fairness Constraintscited by 51
  5. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  6. 2021A New Coreset Framework for Clusteringcited by 38
  7. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  8. 2021Coresets for Classification -- Simplified and Strengthenedcited by 28
  9. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  10. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  11. 2018varepsilon-Coresets for Clustering (with Outliers) in Doubling Metricscited by 19
  12. 2020Coresets for Clustering in Excluded-minor Graphs and Beyondcited by 14
11 more
  1. 2017On the Local Structure of Stable Clustering Instancescited by 13
  2. 2020On Approximability of Clustering Problems Without Candidate Centerscited by 13
  3. 2018Optimal terminal dimensionality reduction in Euclidean spacecited by 11
  4. 2019Fast and Accurate Least-Mean-Squares Solverscited by 10
  5. 2016A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++cited by 8
  6. 2018Composable Core-sets for Determinant Maximization Problems via Spectral Spannerscited by 7
  7. 2018Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensionscited by 7
  8. 2019Dimensionality Reduction for Sum-of-Distances Metriccited by 7
  9. 2021Terminal Embeddings in Sublinear Timecited by 6
  10. 2016Terminal Embeddingscited by 5
  11. 2015Solving k-means on High-dimensional Big Datacited by 1

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1; 2024: 3; 2025: 2.

7 papers.

  1. 2024Scalable Learning of Item Response Theory Modelscited by 6
  2. 2023On Generalization Bounds for Projective Clusteringcited by 4
  3. 2024Settling Time vs. Accuracy Tradeoffs for Clustering Big Datacited by 4
  4. 2025A Tight VC-Dimension Analysis of Clustering Coresets with Applicationscited by 4
  5. 2024Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentationcited by 3
  6. 2025A Scalable Global Optimization Algorithm For Constrained Clusteringcited by 1
  7. 2022Improved Coresets for Euclidean k-Meanscited by 0