Misra–Gries Frequent Items
Track possible heavy hitters with bounded counters and certify their frequency error.
Free theory articleTrack possible heavy hitters with bounded counters and certify their frequency error.
Concept & interpretation
In a massive stream of data, it is often impossible to keep track of the frequency of every single item. However, if we are only interested in finding the "heavy hitters" (items that occur very frequently), we can use bounded space. The Misra–Gries algorithm uses a fixed number of counters to find items that appear more than a certain fraction of the time.
Experiment: Test with different budgets
Open the Misra–Gries Frequent Items explorer. Observe how the counter budget affects the number of decrement rounds and the surviving candidates.
- Set Stream to Skewed and Counter budget to 2. See that A ends with a count of 6 and there are 2 decrement rounds.
- Change the Counter budget to 1. Notice that the decrement rounds increase to 4. A still survives, but its lower bound count drops to 4.
- Set the stream to Balanced (ABCDABCD) with budget 2. The final counters hold C:1 and D:1, but the true counts for all items are 2. Since 2 is not greater than the threshold of 8 / 3 (2.66), there are no true heavy hitters.
- Adjust the Prefix control to see how the counters evolve step-by-step before reaching the end of the stream.