Can I read An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems on EtoBox?

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems by Bhattacharyya, Arnab; Dey, Palash; Woodruff, David P. is a scholarly article available to read on EtoBox.

What is An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems about?

We give the first optimal bounds for returning the $\ell_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, \dots, n\}$ and parameters $0 < \epsilon < \phi \leq 1$, let $f_i$ denote the frequency of item $i$, i.e., the number of times item $i$ occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items $i$ for which $f_i \geq \phi m$, returns no items $j$ for which $f_j \leq (\phi -\epsilon)m$, and returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq \epsilon m$ for each item $i$ that it returns. Our algorithm uses $O(\epsilon^{-1} \log\phi^{-1} + \phi^{-1} \log n + \log \log m)$ bits of space, processes each stream update in $O(1)$ worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive $\epsilon m$ error in the above amount of space, resolving Question 3 in the IITK 2

Author

Bhattacharyya, Arnab; Dey, Palash; Woodruff, David P.

Published

2016

Language

EN