The Heavy Hitter Oracle: Enhancing Frequency Estimation in Skewed Data Streams

Estimating element frequencies in data streams is a fundamental problem when processing large amounts of data. Recent approaches suggest learning-augmented algorithms that can access a heavy-hitter oracle that knows the most frequent elements. In this paper, we challenge the idea of these complex oracles: First, we show that heavy-hitter predictions do not necessarily yield significant efficiency gains in frequency estimation. We prove that a classical algorithm using slightly more memory, $\Theta(B \log B)$ instead of $\Theta(B)$, matches the performance of learning-augmented methods with perfect predictions. Furthermore, we show that given (perfect) predictions, a trivial mechanism achieves the same performance as state-of-the-art learning-augmented algorithms. On the algorithmic side, we introduce SpaceR, a single-pass algorithm that matches the accuracy of existing two-pass prediction-based methods without requiring any predictions. SpaceR uses randomized sampling to identify and track frequent elements in one pass through the data, achieving near-perfect frequency recovery with minimal memory on both synthetic and real-world datasets.