# Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 24 Jun 2024.

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

- [Efficient Processing of Deep Neural Networks: A Tutorial and Survey](https://mlsanity.com/paper/1703.09039/) (2017)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [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)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [ESE: Efficient Speech Recognition Engine with Sparse LSTM on FPGA](https://mlsanity.com/paper/1612.00694/) (2016)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Distortion-Oblivious Algorithms for Minimizing Flow Time](https://mlsanity.com/paper/2109.08424/) (2021)
- [Uniform Bounds for Scheduling with Job Size Estimates](https://mlsanity.com/paper/2110.00633/) (2021)
- [Queues with Small Advice](https://mlsanity.com/paper/2006.15463/) (2020)
- [Data Driven Resource Allocation for Distributed Learning](https://mlsanity.com/paper/1512.04848/) (2015)
- [Ribbon filter: practically smaller than Bloom and Xor](https://mlsanity.com/paper/2103.02515/) (2021)
- [SpaceSaving^±: An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model](https://mlsanity.com/paper/2112.03462/) (2021)

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

- [Learning-Augmented Frequency Estimation in Sliding Windows](https://mlsanity.com/paper/2409.11516/) (2024)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams](https://mlsanity.com/paper/2505.19561/) (2025)

## Abstract (arXiv)

Identifying heavy hitters and estimating the frequencies of flows are fundamental tasks in various network domains. Existing approaches to this challenge can broadly be categorized into two groups, hashing-based and competing-counter-based. The Count-Min sketch is a standard example of a hashing-based algorithm, and the Space Saving algorithm is an example of a competing-counter algorithm. Recent works have explored the use of machine learning to enhance algorithms for frequency estimation problems, under the algorithms with prediction framework. However, these works have focused solely on the hashing-based approach, which may not be best for identifying heavy hitters. In this paper, we present the first learned competing-counter-based algorithm, called LSS, for identifying heavy hitters, top k, and flow frequency estimation that utilizes the well-known Space Saving algorithm. We provide theoretical insights into how and to what extent our approach can improve upon Space Saving, backed by experimental results on both synthetic and real-world datasets. Our evaluation demonstrates that LSS can enhance the accuracy and efficiency of Space Saving in identifying heavy hitters, top k, and estimating flow frequencies.