# Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2021.

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

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [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)

Streaming computation plays an important role in large-scale data analysis. The sliding window model is a model of streaming computation which also captures the recency of the data. In this model, data arrives one item at a time, but only the latest W data items are considered for a particular problem. The goal is to output a good solution at the end of the stream by maintaining a small summary during the stream. In this work, we propose a new algorithmic framework for designing efficient sliding window algorithms via bucketing-based sketches. Based on this new framework, we develop space-efficient sliding window algorithms for k-cover, k-clustering and diversity maximization problems. For each of the above problems, our algorithm achieves (1± varepsilon)-approximation. Compared with the previous work, it improves both the approximation ratio and the space.