# Streaming Euclidean k-median and k-means with o(log n) Space

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

## Key facts

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

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

- [Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models](https://mlsanity.com/paper/2412.07435/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling](https://mlsanity.com/paper/2607.00773/) (2026)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Active Learning with Low-Rank Structure for Data Selection](https://mlsanity.com/paper/2606.16045/) (2026)

## Abstract (arXiv)

We consider the classic Euclidean k-median and k-means objective on data streams, where the goal is to provide a (1+varepsilon)-approximation to the optimal k-median or k-means solution, while using as little memory as possible. Over the last 20 years, clustering in data streams has received a tremendous amount of attention and has been the test-bed for a large variety of new techniques, including coresets, the merge-and-reduce framework, bicriteria approximation, sensitivity sampling, and so on. Despite this intense effort to obtain smaller sketches for these problems, all known techniques require storing at least Omega(log(nDelta)) words of memory, where n is the size of the input and Delta is the aspect ratio. A natural question is if one can beat this logarithmic dependence on n and Delta. In this paper, we break this barrier by first giving an insertion-only streaming algorithm that achieves a (1+varepsilon)-approximation to the more general (k,z)-clustering problem, using tildeOleft(fracdkvarepsilon2right)·(2zlog z)·minleft(frac1varepsilonz,kright)·poly(loglog(nDelta)) words of memory. Our techniques can also be used to achieve two-pass algorithms for k-median and k-means clustering on dynamic streams using tildeOleft(frac1varepsilon2right)·poly(d,k,loglog(nDelta)) words of memory.