Finding Heavy-Hitters with Optimal State Changes

A recent work, [Jayaram, Woodruff, Zhou '24] studied the problem of designing streaming algorithms with few changes memory. In particular they showed that one can solve the ε-l k -heavy-hitters problem using O(1/ε n 1-1/k polylog(n/ε)) state changes and O(poly(1/ε) log n) space, although the log factors here are too large for reasonable implementation. Our first result is a new algorithm for solving the l k heavy hitters problem for k ∈ [1,2]. Our algorithm requires only O(1/ε n 1-1/k poly(log log n)log 1/ε) state changes and O(1/ ε k polylog(n)) space. We also extend our algorithm to k ≥ 2, giving the same state change bound, but with an additional n 1-2/k factor in the space. Finally, we complement this result by a lower bound showing that our state change complexity is optimal up to log log n factors. At the core of our improved algorithm is a new, and very simple algorithm for solving heavy-hitters in insertion only streams, which may be of independent interest.