Heavy Hitter

Problem

Given a stream of elements $S = \{ x_1, x_2, ..., x_n \}$ each from a finite domain $U$, the goal of the heavy hitter problem is to find the elements that appear at least $n / (k + 1) + 1$ times in $S$. Note that there can be at most $k$ such elements.

The Misra-Gries Summary

If false positive is allowed, we have a deterministic algorithm that has $O(k)$ space overhead.

L = {}
for x in S:
    if x in L:
        L[x] = L[x] + 1
    elif len(L) < k:
        L[x] = 1
    else:
        decrement the value of every elements in L by 1
        delete elements in L with value = 0

To see the correctness of the algorithm, we give each element in $S$ a token. There are $n$ tokens in total. If a element is not added to the list $L$, $k + 1$ token are throw away. If an elements appears more than $n / (k + 1)$ times, it must appears in $L$ when the algorithm terminates.

Another way to prove this is that, each time an element is thrown away, it is not in the counter and the sum of counter decremented is $k$. Let $f_x$ be the frequency of an element $x$. Then the maximum number of times $x$ is thrown away is bounded by $k f_x \le n - f_x$, which implies that $f_x \le \frac{n}{k + 1}$.

Count-Min Sketch

An alternate approach is randomized algorithm. In high level, we would like to maintain a set of $m$ bins and assign each element in $U$ uniformly at random one of the bins. Then we put each number in $S$ into the $m$ bins according which bin it is assigned to. In expectation, each bin will receive $\frac{n}{m}$ elements. To estimate the number of time an element $x$ appears in $S$, we just return the number of elements of the bin $x$ is assigned. Note that we might overestimate $x$'s frequency, whose expectation is at most $\frac{n}{m}$. We might repeat this several time to reduce variance.

The tools to achieve the idea are $t$ hash functions $h_1, h_2, ..., h_t : S \rightarrow [m]$. Initially, we have $l$ list (denoted as $L_1, L_2, .., L_t$) where each list has size $m$. Then we go through elements in $S$. For each element $x$, we increment the $L_i[h_i(x)]$ by 1 for all $i \in [t]$. Finally for an element $x$, we use the minimum value $\min_i \{ L_i[h_i(x)] \}$ as its frequency estimation.

By Markov inequality,

Therefore,

which decreases exponentially with respect to the size of $t$.

If we would like the failure probability to be $\delta$, we need to set $t = O(\log \frac{1}{\delta})$.

In conclusion, we can return the estimation of frequency of elements, such that $\forall x \in U$, $\tilde{f_x} \le f_x + 2\frac{n}{m}$, with probability at least $1 - \delta$ and space overhead $O(m \log \frac{1}{\delta})$.

Reference

[1] MIT 6.854/18.415: Advanced Algorithms, Spring 2016, Lecture 4