Wait, What?
You can identify every truly frequent item in a massive stream without storing the stream—and without even storing every distinct item.
The Misra–Gries algorithm is a classic deterministic method for the heavy-hitters problem. It keeps only a bounded set of counters, repeatedly cancels groups of distinct items, and guarantees that anything frequent enough survives as a candidate. The algorithm is a powerful lesson in streaming because its memory bound comes from an invariant, not from luck or random sampling.
Quick Answer
Learn Misra–Gries through majority vote → heavy hitters → k−1 counters → cancellation → candidate guarantee → second-pass verification → error bounds → implementation cost → comparison with sketches → production variants. The key mental model is that a full counter table plus a new unseen item lets us delete one occurrence of k distinct values without changing which item could exceed the n/k threshold.
1. Begin With the Majority Problem
If one value appears more than half the time, Boyer–Moore majority vote can keep one candidate and cancel different values against each other. Misra–Gries generalizes that idea.
Instead of asking for an item occurring more than n/2 times, choose an integer k ≥ 2 and ask for every item whose true frequency is greater than n/k. Such items are often called heavy hitters or frequent items.
2. Why k−1 Counters Are Enough
There cannot be k different items each occurring more than n/k times: together they would require more than n positions. Therefore at most k−1 true heavy hitters can exist.
Misra–Gries maintains at most k−1 candidate counters. That memory budget is not arbitrary; it matches the maximum number of possible answers.
3. The Streaming Rule
misra_gries(stream, k):
counters = empty map
for x in stream:
if x in counters:
counters[x] += 1
else if size(counters) < k - 1:
counters[x] = 1
else:
for each y in counters:
counters[y] -= 1
if counters[y] == 0:
remove y
return keys(counters)Three cases are doing three different jobs: reinforce an existing candidate, admit a new candidate while space exists, or perform a global cancellation when the table is full.
4. Cancellation Is the Proof Idea
Suppose the table already contains k−1 distinct candidates and a new item x arrives that is different from all of them. Decrementing all counters can be interpreted as deleting one occurrence of each stored candidate plus the new item: k distinct items are cancelled together.
A true heavy hitter with frequency greater than n/k cannot be completely erased by repeatedly deleting groups containing at most one copy of it. There can be at most floor(n/k) complete groups of k cancelled items, so an item occurring more than n/k times must remain represented among the final candidates.
5. Candidate Does Not Mean Confirmed Heavy Hitter
The first pass guarantees no false negatives above the threshold: every item with frequency greater than n/k appears in the final candidate set. But some surviving candidates may have lower true frequency.
If the original stream can be scanned again, make a second pass and count the true frequency of only the surviving candidates. Then discard any whose count is not greater than n/k. This turns the candidate guarantee into an exact answer.
6. Trace a Tiny Example
Let k = 3, so we keep at most two counters. Process:
A, B, A, C, A, B, A, D, A
Start with A:1, then B:1. The next A makes A:2. When C arrives and both slots are occupied, cancel one A, one B and C: counters become A:1 and B disappears. Continue. A repeatedly rebuilds its count because it truly dominates the stream.
The useful learning move is to record two views side by side: the physical counters and the conceptual groups of distinct items being cancelled. The second view explains correctness.
7. Residual Counters Underestimate True Frequency
Whenever a global decrement happens, a stored item loses one from its maintained count even though the item did occur in the stream. Therefore the residual counter is generally a lower estimate of the true frequency.
If D global decrement rounds occurred, each item’s true frequency exceeds its residual counter by at most D. Since each decrement round accounts for k stream items, D ≤ n/k. This is the source of the familiar additive-error interpretation of the algorithm.
8. The Hidden Implementation Question: What Does “Decrement All” Cost?
The simple pseudocode touches every stored counter during a full-table cancellation. With k−1 counters, that step is O(k) if implemented literally. For small fixed k, this is often perfectly acceptable and very clear.
For large k or high-throughput systems, production implementations use more careful data structures, batching, offsets or related frequent-item algorithms to reduce update overhead. Always separate the mathematical memory guarantee from the concrete cost of the chosen counter representation.
9. Misra–Gries Is Deterministic
Unlike many probabilistic sketches, the classic Misra–Gries guarantee does not depend on a random hash function or a probability of failure. For an insertion-only stream, the candidate property follows deterministically from cancellation.
This makes it especially useful pedagogically: learners can prove the guarantee directly, then compare it with randomized frequency estimators and understand what different algorithms trade for speed, memory and query flexibility.
10. Compare It With Count-Min Sketch
Misra–Gries keeps a small explicit set of candidate identities. Count-Min Sketch instead hashes all updates into several compact counter arrays and estimates frequencies probabilistically. Count-Min is excellent for point-frequency estimation over a huge universe, while Misra–Gries directly targets the frequent-item candidate problem.
Do not say one “replaces” the other. Their output contracts differ. Professional algorithm selection starts by asking whether you need candidate identities, estimated frequency for arbitrary keys, deterministic guarantees, mergeability, weighted updates or turnstile support.
11. Production Variants and Libraries
Modern streaming libraries build on the same frequent-item lineage while adding engineering for weighted updates, bounded error reporting, serialization and distributed processing. Apache DataSketches’ Frequent Items implementation explicitly cites Misra and Gries (1982) among its foundations and exposes lower and upper frequency bounds for retained items.
That is an important professional distinction: the production data structure may be a refined variant rather than the literal classroom pseudocode. Learn the invariant first, then read the library contract before assuming identical update costs or guarantees.
12. Streaming Changes the Meaning of “Verification”
If the data source is replayable, a second pass can verify exact counts. If the stream is truly one-shot, exact verification may be impossible without storing additional information. The algorithm still provides a bounded candidate set, but the system design must decide whether approximate counts are sufficient or whether upstream storage enables replay.
13. How to Learn It Efficiently
Use subgoal-labelled traces: recognize candidate → use empty slot → cancel a distinct group → remove zeros → verify survivors. Programming-education studies on worked examples show that explicitly labelling procedural subgoals can improve early problem solving, while code-tracing research highlights how learners struggle when several state changes interact. Misra–Gries is ideal for practising disciplined state tables because every update changes only a small bounded map.
Common Failure States
- Keeping k counters instead of k−1 for the n/k guarantee.
- Treating final candidates as automatically verified heavy hitters.
- Forgetting to delete counters that fall to zero.
- Decrementing when an empty counter slot is still available.
- Claiming the maintained counter equals the true frequency.
- Calling the algorithm probabilistic even though the classic guarantee is deterministic.
- Ignoring the O(k) cost of a literal decrement-all implementation.
- Assuming a production frequent-items sketch has exactly the same mechanics as textbook Misra–Gries.
Practice Ladder
- Beginner: trace the k=2 case and connect it to majority vote.
- Foundation: trace k=3 and k=4 streams with explicit cancellation groups.
- Intermediate: implement the first pass and a replay-based verification pass.
- Advanced: prove the n/k candidate guarantee and derive the additive residual-count error.
- Professional: compare Misra–Gries with Count-Min Sketch, Space-Saving and a production frequent-items library under the same workload contract.
- Verification: generate random streams, compute exact frequencies with a full dictionary, and confirm that every item above n/k appears in the candidate set.
Learning Hall Boundary
This article owns Misra–Gries as the deterministic bounded-memory frequent-items algorithm: counter cancellation, the n/k heavy-hitter guarantee, verification and implementation trade-offs. It does not replace the existing general streaming-algorithm, Count-Min/HyperLogLog, majority-vote, MindOS, Bolt or Student/Studying Interface canonical jobs.
Evidence Boundary
The foundational source is Jayadev Misra and David Gries, Finding Repeated Elements, Science of Computer Programming 2 (1982), which presents algorithms for finding values occurring more than n/k times with bounded extra space. Modern heavy-hitter research continues this line, including surveys and results summarized by IBM Research. Apache DataSketches’ current Frequent Items documentation identifies its implementation as a variant in the Misra–Gries family and documents deterministic frequency bounds. The learning design here also draws on programming-education research on subgoal-labelled worked examples and code tracing.
Professional rule: you understand Misra–Gries when you can explain cancellation as removal of k distinct items, prove why a true heavy hitter must survive, and state exactly what the first pass guarantees—and what it does not.
