Research map / Bandits and online learning / Online convex optimization and games
The Heavy Hitter Oracle: Enhancing Frequency Estimation in Skewed Data Streams
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Challenges the value of learned heavy-hitter oracles for frequency estimation in data streams, showing their predictions do not necessarily yield significant efficiency gains.
Problem
Frequency estimation in data streams with learning-augmented algorithms that rely on a heavy-hitter oracle predicting the most frequent elements.
Approach
Shows that heavy-hitter predictions do not necessarily yield significant efficiency gains in frequency estimation, challenging the complexity of existing heavy-hitter oracles; the abstract is truncated so the proposed alternative is not fully stated.
Surprising findings
- Heavy-hitter predictions do not necessarily yield significant efficiency gains in frequency estimation.
Experimental setup
Builds on: learning-augmented frequency estimation
Closest papers by meaning
- Learning-Augmented Frequent Directions (ICLR 2025 · similarity 0.92)
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.84)
- Learning-Augmented Search Data Structures (ICLR 2025 · similarity 0.84)
- Learning-Augmented Dynamic Submodular Maximization (NeurIPS 2024 · similarity 0.83)
- Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters (NeurIPS 2024 · similarity 0.82)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.