# Clustering High Dimensional Dynamic Data Streams

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

## Key facts

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

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error](https://mlsanity.com/paper/2105.15007/) (2021)

## Abstract (arXiv)

We present data streaming algorithms for the k-median problem in high-dimensional dynamic geometric data streams, i.e. streams allowing both insertions and deletions of points from a discrete Euclidean space 1, 2, ldots Deltad. Our algorithms use k ε-2 poly(d log Delta) space/time and maintain with high probability a small weighted set of points (a coreset) such that for every set of k centers the cost of the coreset (1+ε)-approximates the cost of the streamed point set. We also provide algorithms that guarantee only positive weights in the coreset with additional logarithmic factors in the space and time complexities. We can use this positively-weighted coreset to compute a (1+ε)-approximation for the k-median problem by any efficient offline k-median algorithm. All previous algorithms for computing a (1+ε)-approximation for the k-median problem over dynamic data streams required space and time exponential in d. Our algorithms can be generalized to metric spaces of bounded doubling dimension.