Beating CountSketch for Heavy Hitters in Insertion Streams

Given a stream $p_1,\dots ,p_m$ of items from a universe $\mathcal{U}$, which, without loss of generality we identify with the set of integers ${1, 2, \ldots, n}$,weconsidertheproblemofreturningall$\ell_2$-heavy hitters, i.e., those items $j$ for which $f_j\ge ϵ\sqrt{F_2}$, where $f_j$ is the number of occurrences of item $j$ in the stream, and $F_2 = \sum_{i \in [n]} f_i^2$\mathrm{.}Suchaguaranteeisconsiderablystrongerthanthe$\ell_1$-guarantee,whichfindsthose$j$forwhich$f_j \geq \epsilon m$. In 2002, Charikar, Chen, and Farach-Colton suggested the {\sf CountSketch} data structure, which finds all such $j$ using $\mathrm{\Theta }({\log }^{2}n)$ bits of space (for constant $ϵ>0$). The only known lower bound is $\mathrm{\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 $F_2$ simultaneously at all points in a stream using only $O(\log n\log \log n)$ bits of space, improving a natural union bound and the algorithm of Huang, Tai, and Yi (2014). (2) A way to estimate the ${\mathrm{\ell }}_{\mathrm{\infty }}$ norm of a stream up to additive error $ϵ\sqrt{F_2}$ with $O(\log n\log \log n)$ bits of space, resolving Open Question 3 from the IITK 2006 list for insertion only streams.