# Coresets and Sketches

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2016.

## Built on by (most cited first, 30 of 63)

- [LESS: Selecting Influential Data for Targeted Instruction Tuning](https://mlsanity.com/paper/2402.04333/) (2024)
- [SemDeDup: Data-efficient learning at web-scale through semantic deduplication](https://mlsanity.com/paper/2303.09540/) (2023)
- [Dataset Condensation via Efficient Synthetic-Data Parameterization](https://mlsanity.com/paper/2205.14959/) (2022)
- [Skill-it! A Data-Driven Skills Framework for Understanding and Training Language Models](https://mlsanity.com/paper/2307.14430/) (2023)
- [Efficient Dataset Distillation Using Random Feature Approximation](https://mlsanity.com/paper/2210.12067/) (2022)
- [DsDm: Model-Aware Dataset Selection with Datamodels](https://mlsanity.com/paper/2401.12926/) (2024)
- [How to Train Data-Efficient LLMs](https://mlsanity.com/paper/2402.09668/) (2024)
- [Dataset Condensation with Latent Space Knowledge Factorization and Sharing](https://mlsanity.com/paper/2208.10494/) (2022)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [FisherSFT: Data-Efficient Supervised Fine-Tuning of Language Models Using Information Gain](https://mlsanity.com/paper/2505.14826/) (2025)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [FairDeDup: Detecting and Mitigating Vision-Language Fairness Disparities in Semantic Dataset Deduplication](https://mlsanity.com/paper/2404.16123/) (2024)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Preemptively Pruning Clever-Hans Strategies in Deep Neural Networks](https://mlsanity.com/paper/2304.05727/) (2023)
- [In2Core: Leveraging Influence Functions for Coreset Selection in Instruction Finetuning of Large Language Models](https://mlsanity.com/paper/2408.03560/) (2024)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Federated Wasserstein Distance](https://mlsanity.com/paper/2310.01973/) (2023)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [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)
- [Deep Active Learning in the Presence of Label Noise: A Survey](https://mlsanity.com/paper/2302.11075/) (2023)
- [AutoCoreset: An Automatic Practical Coreset Construction Framework](https://mlsanity.com/paper/2305.11980/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Dataset Distillation for Histopathology Image Classification](https://mlsanity.com/paper/2408.09709/) (2024)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)

## Abstract (arXiv)

Geometric data summarization has become an essential tool in both geometric approximation algorithms and where geometry intersects with big data problems. In linear or near-linear time large data sets can be compressed into a summary, and then more intricate algorithms can be run on the summaries whose results approximate those of the full data set. Coresets and sketches are the two most important classes of these summaries. We survey five types of coresets and sketches: shape-fitting, density estimation, high-dimensional vectors, high-dimensional point sets / matrices, and clustering.