An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems by Arnab Bhattacharyya, Palash Dey, David P. Woodruff
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 2006 Workshop on Algorithms for Data Streams for the case of $\ell_1$-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and 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 frequency of an item.
BPTree: an $\ell_2$ heavy hitters algorithm using constant memory by Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, David P. Woodruff, Zhengyu Wang
The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. In sub-polynomial space, the strongest guarantee available is the $\ell_2$ guarantee, which requires finding all items that occur at least $\varepsilon\|f\|_2$ times in the stream, where the $i$th coordinate of the vector $f$ is the number of occurrences of $i$ in the stream. The first algorithm to achieve the $\ell_2$ guarantee was the CountSketch of [CCF04], which for constant $\varepsilon$ requires $O(\log n)$ words of memory and $O(\log n)$ update time, and is known to be space-optimal if the stream allows for deletions. The recent work of [BCIW16] gave an improved algorithm for insertion-only streams, using only $O(\log\log n)$ words of memory.
In this work, we give an algorithm "BPTree" for $\ell_2$ heavy hitters in insertion-only streams that achieves $O(1)$ words of memory and $O(1)$ update time for constant $\varepsilon$, which is optimal. In addition, we describe an algorithm for tracking $\|f\|_2$ at all times with $O(1)$ memory and update time. Our analyses rely on bounding the expected supremum of a Bernoulli process involving Rademachers with limited independence, which we accomplish via a Dudley-like chaining argument that may have applications elsewhere.
Approximate Hamming distance in a stream by Raphael Clifford, Tatiana Starikovskaya
We consider the problem of computing a $(1+\epsilon)$-approximation of the Hamming distance between a pattern of length $n$ and successive substrings of a stream. We first look at the one-way randomised communication complexity of this problem, giving Alice the first half of the stream and Bob the second half. We show the following: (1) If Alice and Bob both share the pattern then there is an $O(\epsilon^{-4} \log^2 n)$ bit randomised one-way communication protocol. (2) If only Alice has the pattern then there is an $O(\epsilon^{-2}\sqrt{n}\log n)$ bit randomised one-way communication protocol.
We then go on to develop small space streaming algorithms for $(1+\epsilon)$-approximate Hamming distance which give worst case running time guarantees per arriving symbol. (1) For binary input alphabets there is an $O(\epsilon^{-3} \sqrt{n} \log^{2} n)$ space and $O(\epsilon^{-2} \log{n})$ time streaming $(1+\epsilon)$-approximate Hamming distance algorithm. (2) For general input alphabets there is an $O(\epsilon^{-5} \sqrt{n} \log^{4} n)$ space and $O(\epsilon^{-4} \log^3 {n})$ time streaming $(1+\epsilon)$-approximate Hamming distance algorithm.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment