Misra-Gries heavy-hitters algorithm

one of the earliest data streaming algorithm.

problem.

Given the bag $b$ of $n$ elements and an integer $k \geq 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 \geq 2$

pseudocode.

$"\\begin{algorithm}\n\\caption{Misra--Gries}\n\\begin{algorithmic}\n\\State $t \\gets \\{\\}$\n\\State $d \\gets 0$\n\\For{$i \\gets 0$ to $n-1$}\n \\If{$b[i] \\notin t$}\n \\State $t \\gets t \\cup \\{b[i]\\}$\n \\State $d \\gets d + 1$\n \\Else\n \\State $t \\gets t \\cup \\{b[i]\\}$\n \\EndIf\n \\If{$d = k$}\n \\State Delete $k$ distinct values from $t$\n \\State Update $d$\n \\EndIf\n\\EndFor\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 3 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