Misra-Gries heavy-hitters algorithm

one of the earliest data streaming algorithm.

problem.

Given the bag $b$ of $n$ elements and an integer $k\ge 2$. Find the values that occur more than $n/k$ times in $b$

idea: two passes over the values in $b$, while storing at most $k$ values from $b$ and their number of occurrences.

Assume the bag is available in array $b[0:n-1]$ of $n$ elements, then a heavy-hitter of bag $b$ is a value that occurs more than $n/k$ times in $b$ for some integer $k\ge 2$

pseudocode.

Algorithm 2 Misra--Gries

1:$t \gets \{\}$

2:$d \gets 0$

3:for $i \gets 0$ to $n-1$ do

4:if $b[i] \notin t$ then

5:$t \gets t \cup \{b[i]\}$

6:$d \gets d + 1$

7:else

8:$t \gets t \cup \{b[i]\}$

9:end if

10:if $d = k$ then

11:Delete $k$ distinct values from $t$

12:Update $d$

13:end if

14:end for