# Settling Time vs. Accuracy Tradeoffs for Clustering Big Data

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 63 references that are in the map.
- First posted on arXiv 2 Apr 2024.

## Builds on (most cited first, 19 of 19)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications](https://mlsanity.com/paper/2007.10137/) (2020)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [A Nearly Optimal Size Coreset Algorithm with Nearly Linear Time](https://mlsanity.com/paper/2210.08361/) (2022)
- [Fast and Accurate k-means++ via Rejection Sampling](https://mlsanity.com/paper/2012.11891/) (2020)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [A sampling-based approach for efficient clustering in large datasets](https://mlsanity.com/paper/2112.14793/) (2021)
- [On the Fixed-Parameter Tractability of Capacitated Clustering](https://mlsanity.com/paper/2208.14129/) (2022)
- [The Power of Uniform Sampling for k-Median](https://mlsanity.com/paper/2302.11339/) (2023)

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

- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)
- [Khatri-Rao Clustering for Data Summarization](https://mlsanity.com/paper/2603.06602/) (2026)

## Abstract (arXiv)

We study the theoretical and practical runtime limits of k-means and k-median clustering on large datasets. Since effectively all clustering methods are slower than the time it takes to read the dataset, the fastest approach is to quickly compress the data and perform the clustering on the compressed representation. Unfortunately, there is no universal best choice for compressing the number of points - while random sampling runs in sublinear time and coresets provide theoretical guarantees, the former does not enforce accuracy while the latter is too slow as the numbers of points and clusters grow. Indeed, it has been conjectured that any sensitivity-based coreset construction requires super-linear time in the dataset size. We examine this relationship by first showing that there does exist an algorithm that obtains coresets via sensitivity sampling in effectively linear time - within log-factors of the time it takes to read the data. Any approach that significantly improves on this must then resort to practical heuristics, leading us to consider the spectrum of sampling strategies across both real and artificial datasets in the static and streaming settings. Through this, we show the conditions in which coresets are necessary for preserving cluster validity as well as the settings in which faster, cruder sampling strategies are sufficient. As a result, we provide a comprehensive theoretical and practical blueprint for effective clustering regardless of data size. Our code is publicly available and has scripts to recreate the experiments.