# Near-Optimal k-Clustering in the Sliding Window Model

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

## Key facts

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

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

- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Clustering with Label Consistency](https://mlsanity.com/paper/2512.19654/) (2025)
- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)

## Abstract (arXiv)

Clustering is an important technique for identifying structural information in large-scale data analysis, where the underlying dataset may be too large to store. In many applications, recent data can provide more accurate information and thus older data past a certain time is expired. The sliding window model captures these desired properties and thus there has been substantial interest in clustering in the sliding window model. In this paper, we give the first algorithm that achieves near-optimal (1+varepsilon)-approximation to (k,z)-clustering in the sliding window model, where z is the exponent of the distance function in the cost. Our algorithm uses frackmin(varepsilon4,varepsilon2+z),polylogfracnDeltavarepsilon words of space when the points are from [Delta]d, thus significantly improving on works by Braverman et. al. (SODA 2016), Borassi et. al. (NeurIPS 2021), and Epasto et. al. (SODA 2022). Along the way, we develop a data structure for clustering called an online coreset, which outputs a coreset not only for the end of a stream, but also for all prefixes of the stream. Our online coreset samples frackmin(varepsilon4,varepsilon2+z),polylogfracnDeltavarepsilon points from the stream. We then show that any online coreset requires Omegaleft(frackvarepsilon2log nright) samples, which shows a separation from the problem of constructing an offline coreset, i.e., constructing online coresets is strictly harder. Our results also extend to general metrics on [Delta]d and are near-optimal in light of a Omegaleft(frackvarepsilon2+zright) lower bound for the size of an offline coreset.