Learning-Augmented Sketches for Frequency Estimation
summary
Augments hashing-based frequency sketches with a learned binary oracle (RNN and decision-tree attempts) that flags heavy items after training on a prefix, then stores flagged items in dedicated buckets while feeding others to a Count-Min sketch or CountSketch. Evaluated on hour-long network traces and the AOL query log, it reduces average weighted L1 error for the same total amortized memory (includes model ROM). Theory under Zipf(1) shows asymptotic gains by replacing a global log n factor with log(n/b) and matches a lower bound for hashing estimators.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:02Classical algorithms
- 4:23Related work
- 9:10Q&A and problem setup
- 12:03Count-min algorithm
- 15:13Structure in data
- 19:38Proposed algorithm
- 23:55Experimental setup
- 27:52Experimental results
- 34:41Theoretical analysis
- 39:37Conclusion and Q&A
related talks
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 50mData sketching workshop
01h 26mStreaming, Sketching and Sufficient Statistics II
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
46mSketching Techniques for Kernel Density Estimation
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 05mDistribution Estimation and Applications III