Misra-Gries[1] is one of the earliest streaming algorithms, and it is described below in those terms in section #Summaries.
Henceforth, a heavy hitter of bag b is a value that occurs more than n ÷ k times in it, for some integer k, k≥2.
Using an AVL tree implementation of t, the algorithm has a running time of O(n log k).
Since each counter ci may have a value as high as n, its storage needs O(log n) bits.
In the field of streaming algorithms, the output of the Misra-Gries algorithm in the first pass may be called a summary, and such summaries are used to solve the frequent elements problem in the data stream model.
It processes the elements using at most logarithmic amount of extra space in the size of the list to produce an answer.