Prefer a chat interface with context about you and your work?
An Optimal Algorithm for โ <sub>1</sub> -Heavy Hitters in Insertion Streams and Related Problems
We give the first optimal bounds for returning the โ 1 -heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in { 1, 2, โฆ , n } and parameters 0 โฆ