# Fully Dynamic k-Means Coreset in Near-Optimal Update Time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2024.

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

- [TimeBlocks: Foundational and Continual Time-Series Blockbase -- Extended Version](https://mlsanity.com/paper/2606.02142/) (2026)

## Abstract (arXiv)

We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of tilde O(k) in general metric spaces, which reduces to tilde O(d) in the Euclidean space ℝd. The query time is O(k2) in general metrics, and O(kd) in ℝd. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm update time tilde O(d), and query time tilde O(kd + k2). To maintain a O(polylog~k)-approximation, the query time is reduced to tilde O(kd).