one of the earliest data streaming algorithm.

problem.

Given the bag of elements and an integer . Find the values that occur more than times in

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

Assume the bag is available in array of elements, then a heavy-hitter of bag is a value that occurs more than times in for some integer

pseudocode.

Algorithm 2 Misra--Gries

1:t{}t \gets \{\}

2:d0d \gets 0

3:for i0i \gets 0 to n1n-1 do

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

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

6:dd+1d \gets d + 1

7:else

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

9:end if

10:if d=kd = k then

11:Delete kk distinct values from tt

12:Update dd

13:end if

14:end for