Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams

Rana Shahout, Michael Mitzenmacher

Abstract

Identifying "heavy hitters"—the small subset of items that account for the majority of volume in a data stream—is a fundamental challenge in network monitoring and web analytics. Traditional counter-based algorithms, such as Space Saving (SS), are often limited by "pollution" from a massive tail of infrequent items that displace more significant data. This paper introduces Learned Space Saving (LSS), the first counter-based streaming algorithm to successfully incorporate machine learning predictions. By utilizing ML to filter low-frequency noise and protect predicted heavy hitters, LSS achieves up to 24% higher recall and 34% lower error rates than traditional methods, while maintaining robustness against prediction errors.

Introduction

In high-speed data environments, such as ISP backbones or web search engines, it is impossible to store the frequency of every unique item. Instead, researchers use "sketches"—compact data structures that provide approximate counts. A common problem in these sketches is the "long tail": millions of items that appear only once or twice. In traditional algorithms like Space Saving, these "one-hit wonders" can constantly evict more important items from limited counter slots, leading to significant estimation errors.

While recent advancements have applied machine learning to hashing-based sketches (like Count-Min), counter-based algorithms remained largely unaugmented. This paper bridges that gap by introducing a framework that uses ML predictions to improve accuracy without sacrificing the theoretical guarantees of traditional streaming algorithms.

The Learned Space Saving (LSS) Framework

The authors propose two primary components for LSS that can be deployed independently or in tandem to optimize performance:

1. LSS-LF (Low Frequency Filtering)

LSS-LF addresses the pollution problem by using a predictor to identify items likely to appear with very low frequency. These items are initially diverted to a Counting Bloom Filter (CBF) rather than the main Space Saving table. An item is only promoted to the main counters if its frequency in the CBF exceeds a predefined threshold ($t$). This mechanism ensures that the main counters are reserved for items with a proven history of recurrence.

2. LSS-HH (Heavy Hitter Protection)

LSS-HH uses a predictor to identify likely heavy hitters. These items are assigned to "fixed" counters that are exempt from the standard eviction rules of the Space Saving algorithm. This protection ensures that the counts for the most significant items remain highly accurate and are never reset by transient noise.

3. LSS+ (Throughput Optimization)

To mitigate the computational cost of querying a Bloom filter for every packet, the authors developed LSS+. This version employs probabilistic sampling, updating the filter and counters only a fraction of the time. This significantly increases throughput, making the algorithm more suitable for high-speed networking hardware.

Experimental Methodology

The researchers evaluated LSS against standard Space Saving and other state-of-the-art sketches using three diverse datasets:

  • IP Trace Datasets (CAIDA): Real-world anonymized traffic from a Tier 1 ISP backbone, comprising approximately 30 million packets and 1 million unique flows.
  • Web Search Query Datasets (AOL): A log of 21 million search queries from 650,000 users.
  • Synthetic Datasets: Data generated following a Zipfian distribution to test the algorithm's performance across varying levels of data skewness.

Key Insights and Results

The evaluation demonstrated that LSS consistently outperforms traditional Space Saving across all primary metrics:

  • Improved Accuracy: LSS achieved up to 18% better precision for top-k identification and 24% higher recall for heavy hitters.
  • Error Reduction: The Root Mean Square Error (RMSE) for frequency estimation was reduced by as much as 34%.
  • Robustness to Misprediction: A critical feature of LSS is its safety net. If the ML model incorrectly identifies a heavy hitter as a low-frequency item, the Bloom filter eventually allows the item into the main table once its true frequency is established. Even when tested with intentionally poor predictions, LSS performance remained close to the baseline Space Saving algorithm.
  • Efficiency: Through the LSS+ sampling method, the authors showed that the accuracy gains of learned streaming can be achieved without a prohibitive drop in processing speed.

Discussion and Limitations

While LSS represents a significant step forward, the authors identify several areas for future consideration. The primary challenge is inference latency; running neural network predictions at line rate requires specialized hardware like NPUs or extremely lightweight "oracle" predictors. Additionally, the algorithm's performance is sensitive to the size of the Bloom filter and the threshold ($t$). Future work may explore adaptive thresholds that can adjust dynamically as the underlying data distribution shifts.

Conclusion

Learned Space Saving demonstrates that machine learning can significantly enhance the efficiency of counter-based streaming algorithms. By decoupling the robustness logic (the Bloom filter) from the core algorithm logic, LSS provides a framework that benefits from accurate predictions while remaining resilient to the inherent uncertainty of ML models. This approach offers a more "plug-and-play" solution for heavy hitter tasks compared to traditional hashing-based sketches.

Summary updated

BibTeX
@inproceedings{shahout2024learning,
  author = {Rana Shahout and Michael Mitzenmacher},
  title = {{Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams}},
  booktitle = {ICNP},
  year = {2024},
  doi = {10.1109/icnp61940.2024.10858542},
}
Figure