Research map / Learning theory and algorithms / Clustering
Coresets and dynamic clustering
Use coresets and dynamic data structures for k-center and robust clustering.
77 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Clustering, keyword cluster “center · median · coreset”
State History Tried Checklist Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
18 papers in 2023–24 and 29 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 12.9% to 14.1%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Improving PAC Exploration Using the Median Of Means (NeurIPS 2016 · 10 citations)
- 2017 · PIVE: Per-Iteration Visualization Environment for Real-Time Interactions with Dimension Reduction and Clustering (AAAI 2017 · 18 citations)
- 2018 · Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under $\ell_p$ Distances (ICML 2018 · 21 citations)
- 2019 · Making AI Forget You: Data Deletion in Machine Learning (NeurIPS 2019 · 69 citations)
- 2020 · Coresets for Clustering in Graphs of Bounded Treewidth (ICML 2020 · 7 citations)
- 2021 · Extreme k-Center Clustering (AAAI 2021 · 7 citations)
- 2022 · Improved Coresets for Euclidean $k$-Means (NeurIPS 2022 · 7 citations)
- 2023 · Clustering What Matters: Optimal Approximation for Clustering with Outliers (AAAI 2023 · 11 citations)
- 2024 · Parameterized Approximation Algorithms for Sum of Radii Clustering and Variants (AAAI 2024 · 9 citations)
- 2025 · Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · 1 citation)
- 2026 · Approximation Preserving Coresets (ICML 2026 · 0 citations)
Earliest papers here
- Improving PAC Exploration Using the Median Of Means (NeurIPS 2016 · 10 citations)
- Accelerating Random Kaczmarz Algorithm Based on Clustering Information (AAAI 2016 · 3 citations)
- PIVE: Per-Iteration Visualization Environment for Real-Time Interactions with Dimension Reduction and Clustering (AAAI 2017 · 18 citations)
What has been tried
51 papers here report 285 measured changes (a component added, removed or swapped, compared with a baseline): helped 75%, no clear effect 11%, hurt 8%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use BSparsifier with q = 4/\epsilon instead of the standard sparsifier | Dynamic metric k-center · recourse | O(1) -> 8 + \epsilon | Helped | Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · 1 citation) |
| Add a random shift to the hash function | Kddcup, Covertype, Census, Fashion-MNIST · clustering cost | Helped | Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · 0 citations) | |
| Sample size parameter f reduced (sparser samples, f=1/450) | 6 benchmarks · density | No clear effect | Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · 0 citations) | |
| Use SVD-based core kernels instead of randomly sampled kernel submatrices | Flower17 and DIGIT · kernel weight approximation error | Helped | COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering (ICML 2025) |
What reviewers will expect
Datasets and baselines named in the 18 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- uniform sampling · 2 of 18 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 47 papers; from OpenAlex and the papers' affiliations).
- Central South University · 4 papers
- Google · 4 papers
- Nanjing University · 3 papers
- Peking University · 3 papers
- Eindhoven University of Technology · 3 papers
- KTH Royal Institute of Technology · 2 papers
- Huawei · 2 papers
- University of Warwick · 2 papers
- Nanyang Technological University · 2 papers
- Carnegie Mellon University · 2 papers
Use it
Download BibTeX of 37 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- k-means++ seeding analysis (76 papers)
- Fair clustering approximation (31 papers)
Elsewhere in the topic
- Clustering approximation algorithms (150 papers)
- Incomplete multi-view clustering (125 papers)
- Correlation clustering (102 papers)
- Subspace clustering (102 papers)
- Spectral clustering algorithms (43 papers)
- Fairness-constrained clustering (19 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).