Misra–Gries Frequent Items
Track possible heavy hitters with bounded counters and certify their frequency error.
By Riano · Published · Updated · Report a correction
Misra–Gries Frequent Items
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.
Bounded Counters and Cancellations
Given a stream of length N, we want to find all items that occur more than N / (B + 1) times, using only B counters. The algorithm processes each item as follows:
- If the item already has a counter, increment it.
- If it doesn't, but there is an empty slot (fewer than B active counters), assign it a counter and set it to 1.
- If all B counters are occupied by other items, decrement ALL active counters by 1. Any counter that reaches 0 is removed. Crucially, the arriving item is NOT tracked (it acts as the +1 for the (B+1)th slot which is immediately decremented).
This cancellation process guarantees that if an item appears more than N / (B + 1) times, it must survive the decrements because every decrement round removes B + 1 distinct items (the B counters plus the current item). There can be at most N / (B + 1) such rounds.
Worked example: Skewed stream
Consider the stream "ABAACADABAAA" with 12 items and a counter budget of B = 2. The threshold for a heavy hitter is 12 / (2 + 1) = 4.
| Time | Item | Action | Counters State |
|---|---|---|---|
| 1 | A | Insert | A:1 |
| 2 | B | Insert | A:1, B:1 |
| 3 | A | Update | A:2, B:1 |
| 4 | A | Update | A:3, B:1 |
| 5 | C | Decrement | A:2, (B dropped) |
| 6 | A | Update | A:3 |
| 7 | D | Insert | A:3, D:1 |
| 8 | A | Update | A:4, D:1 |
| 9 | B | Decrement | A:3, (D dropped) |
| 10 | A | Update | A:4 |
| 11 | A | Update | A:5 |
| 12 | A | Update | A:6 |
After processing the stream, the counter for A is 6. There were 2 decrement rounds. The true count of A must be between 6 and 6 + 2 = 8. Since A's true count is exactly 8, the bounds hold. Because 8 > 4, A is a true heavy hitter.
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.
Limitations
The Misra–Gries algorithm produces candidates that might not actually be heavy hitters (false positives). A second pass over the stream is required to count the exact frequencies of the surviving candidates and filter out the false positives.
- The algorithm does not guarantee that a candidate's final counter value equals its true frequency.
- It only provides a lower bound (the final counter value) and an upper bound (counter + total decrement rounds).
- It assumes elements can be perfectly distinguished.
References
The original paper by Misra and Gries introduces this fundamental algorithm for finding repeated elements in a stream using bounded space, laying the groundwork for many later heavy-hitter algorithms in data stream processing.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Misra–Gries Frequent Items module.
Try Misra–Gries Frequent Items on Riano →