Beating CountSketch for Heavy Hitters in Insertion Streams

Given a stream p1, ldots, pm of items from a universe U, which, without loss of generality we identify with the set of integers 1, 2, ldots, n, we consider the problem of returning all ℓ2-heavy hitters, i.e., those items j for which fj ≥ ε √F2, where fj is the number of occurrences of item j in the stream, and F2 = sumi ∈ [n] fi2. Such a guarantee is considerably stronger than the ℓ1-guarantee, which finds those j for which fj ≥ ε m. In 2002, Charikar, Chen, and Farach-Colton suggested the sf CountSketch data structure, which finds all such j using Theta(log2 n) bits of space (for constant ε > 0). The only known lower bound is Omega(log n) bits of space, which comes from the need to specify the identities of the items found. In this paper we show it is possible to achieve O(log n log log n) bits of space for this problem. Our techniques, based on Gaussian processes, lead to a number of other new results for data streams, including (1) The first algorithm for estimating F2 simultaneously at all points in a stream using only O(log nloglog n) bits of space, improving a natural union bound and the algorithm of Huang, Tai, and Yi (2014). (2) A way to estimate the ℓ∞ norm of a stream up to additive error ε √F2 with O(log nloglog n) bits of space, resolving Open Question 3 from the IITK 2006 list for insertion only streams.