New Algorithms for Heavy Hitters in Data Streams
summary
One-pass algorithm finds L2 heavy hitters in insertion-only streams using nearly log N bits of space (previous best was ~log^2 N), giving an optimal bound after removing a log log N slack. It replaces CountSketch signs with Gaussian processes and applies the chaining inequality to bound counter maxima, uses an amplification/partitioning sieve to boost a heavy item's signal, and derandomizes via Johnson–Lindenstrauss and Nisan-style generators; implementations are preliminary.
AI-written summary · about
chapters (6)
- 0:00Start
- 7:26solving the l2 guarantee
- 9:09estimate the frequency of any individual item
- 24:25maintain a signed counter in each bucket
- 33:14define a distance function on these indices
- 47:02the expected maximum value of the counter at any time
related talks
01h 21mAn Overview on Data Streams Algorithms
55mTheory of Data Streams
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 04mSampling Big Ideas in Sublinear Algorithms
32mStreaming Algorithms for Matchings in Low Arboricity Graphs
01h 26mStreaming, Sketching and Sufficient Statistics II
27mStrike gold (and avoid drowning) with streaming algorithms
48mProbabilistic data structures