# Learning-Augmented Frequency Estimation in Sliding Windows

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 20 references that are in the map.
- First posted on arXiv 17 Sep 2024.

## Builds on (most cited first, 5 of 5)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams](https://mlsanity.com/paper/2406.16270/) (2024)
- [Heavy Hitters over Interval Queries](https://mlsanity.com/paper/1804.10740/) (2018)

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

- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)

## Abstract (arXiv)

We show how to utilize machine learning approaches to improve sliding window algorithms for approximate frequency estimation problems, under the ``algorithms with predictions'' framework. In this dynamic environment, previous learning-augmented algorithms are less effective, since properties in sliding window resolution can differ significantly from the properties of the entire stream. Our focus is on the benefits of predicting and filtering out items with large next arrival times -- that is, there is a large gap until their next appearance -- from the stream, which we show improves the memory-accuracy tradeoffs significantly. We provide theorems that provide insight into how and by how much our technique can improve the sliding window algorithm, as well as experimental results using real-world data sets. Our work demonstrates that predictors can be useful in the challenging sliding window setting.