Arnab Bhattacharyya: An Optimal Algorithm for Heavy Hitters in Insertion Streams and Related Problems

Wednesday, October 28, 2015 - 4:00pm to 5:00pm
Arnab Bhattacharyya
Indian Institute of Science
We give the first optimal bounds for returning the 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$ indices in $\{1, 2, \ldots, n\}$ and parameters $0 < \epsilon < \phi \leq 1$, let $f_i$ denote the frequency of index $i$, i.e., the number of times $i$ occurs in the stream. With arbitrarily large constant probability, our algorithm returns all incides $i$ for which $f_i \geq \phi m$, it returns no indices $j$ for which $f_j \leq (\phi -\epsilon)m$, and it returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq \epsilon m$ for each index $i$ that it returns. Our algorithm uses $O(\epsilon^{-1   \log(1/\epsilon) + \phi^{-1} \log n + \log \log m)$ bits of space, it processes each stream update in $O(1)$ time, and it can report its output in time linear in the output size. We also prove a lower bound, showing that our algorithm is optimal up to a constant factor in its space complexity. Our algorithm can be used to estimate the maximum frequency of any item up to an additive $\epsilon m$ error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by applications in voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the most frequent items.
Joint work with Palash Dey and David Woodruff.