Improved Frequency Estimation Algorithms with and without Predictions
summary
Tight characterization shows learned CountMin/CountSketch only help when space B is very large; a new algorithm uses many tiny sketches plus one large sketch to get strictly better worst-case and Zipfian-average error in some realistic B regimes without any predictions, and further reduces error when given heavy-hitter predictions. The method hashes into log log n small sketches to decide whether to output 0 or consult the large table, yields failure probability ≈ 1/log n, and beats prior learned and classical methods on packet and search traces.
AI-written summary · about
chapters (7)
- 0:00Introduction to problem
- 1:31Assumptions and background
- 2:36Prior work and motivation
- 7:01New research contributions
- 9:31Algorithm design
- 16:00Analysis and results
- 22:30Q&A and conclusion
related talks
39mModel Counting Meets Distinct Estimation
10mDon’t forget to sketch! Running with large datasets
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
18mDifferentially Private Continual Releases of Streaming Frequency Moment Estimations
01h 00mCount-min Sketch to Infinity
29mFactorized Graph Neural Networks (With Some Algebraic Cheating)
41mProbabilistic Data Structures
31mAnswering Multi-dimensional Queries on Massive Datasets