2
$\begingroup$

I was shown this problem from a class last year and I am still not sure what the right answer is.

Items that occur with high frequency in a dataset are sometimes called heavy hitters. Accordingly, let us define the HEAVY-HITTERS problem, with real parameter $\varepsilon>0$, as follows. The input is a stream $\sigma$. Let $m, n, f$ have their usual meanings. Let $$ \mathrm{HH}_{\varepsilon}(\sigma)=\left\{j \in[n]: f_{j} \geq \varepsilon m\right\} $$ be the set of $\varepsilon$-heavy hitters in $\sigma$. Modify Misra-Gries to obtain a one-pass streaming algorithm that outputs this set "approximately" in the following sense: the set $H$ it outputs should satisfy $$ \mathrm{HH}_{\varepsilon}(\sigma) \subseteq H \subseteq \mathrm{HH}_{\varepsilon / 2}(\sigma) $$ Your algorithm should use $O\left(\varepsilon^{-1}(\log m+\log n)\right)$ bits of space.

How can you do this?

I found a paper by Manku and Motwani but it isn't a modification of Misra-Gries as far as I can see. From the stated complexity it looks like you should set $k=\frac{1}{\epsilon}$ and run a constant number of copies of Misra-Gries but I can't get that to work.

$\endgroup$
1
  • 2
    $\begingroup$ Please don't delete questions after they have received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful to others in the future, so deleting your question after it has been answered can be considered impolite to the person who took the time to write an answer. $\endgroup$
    – D.W.
    Oct 10, 2021 at 0:43

1 Answer 1

2
$\begingroup$

Choose $k = 2/\epsilon$, and output all items satisfying $\hat{f}_j \geq \frac{\epsilon}{2}m$.

The final estimates satisfy $$ f_j - \frac{\epsilon}{2} m \leq \hat{f}_j \leq f_j. $$ If $j \in \mathrm{HH}_\epsilon(\sigma)$ then $\hat{f}_j \geq \epsilon m - \frac{\epsilon}{2} m = \frac{\epsilon}{2} m$, and so we output $j$. Conversely, if we output $j$ then $f_j \geq \hat{f}_j \geq \frac{\epsilon}{2} m$, and so $j \in \mathrm{HH}_{\epsilon/2}(\sigma)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.