Top-K and heavy hitters: Misra-Gries and Space-Saving

How do you find the most frequent items in fixed memory, and what does the answer not guarantee?

A heavy hitter is an item whose frequency exceeds a threshold fraction of the stream. Finding the "top K" items is the same problem.

Misra-Gries. Keep k counters. For each arriving item:

• if it is tracked, increment its counter;
• else, if a free slot exists, start a counter at 1;
• else decrement every counter by one and drop those that reach zero.

Any item with frequency above N/(k + 1) is guaranteed to survive, and each counter underestimates by at most N/(k + 1). It is deterministic: no failure probability, no hash functions, no δ.

def misra_gries(stream, k):
    counters = {}
    for x in stream:
        if x in counters:
            counters[x] += 1
        elif len(counters) < k:
            counters[x] = 1
        else:
            for key in list(counters):
                counters[key] -= 1
                if counters[key] == 0:
                    del counters[key]
    return counters

Space-Saving. Keep k counters. When an untracked item arrives and all slots are taken, evict the minimum counter and give the new item that count plus 1. It overestimates by at most the evicted minimum. It has better practical accuracy on skewed streams and is a natural fit for "give me the top k".

Look at the eviction rule: discard the element that is dominated on the only dimension that matters. This is the same domination-pruning logic as the monotonic deque in Ordering structures. It is the second appearance of "retain only the undominated candidates" as a state-reduction technique, here with a bounded and known error.

The guarantee people assume and do not have. Both structures guarantee that items below the frequency threshold cannot appear in the answer. Neither guarantees the ordering inside the returned top-k. If you rank the output and show positions 1 through 10 as a leaderboard, you are reading noise between neighbors whose true counts are within the error bound.

Versus Count-Min, the decision rule is clean. Misra-Gries and Space-Saving give error N/k deterministically in k counters. Count-Min gives error ε · N probabilistically in (e/ε) · ln(1/δ) counters. For pure heavy hitters, Misra-Gries and Space-Saving are smaller and deterministic, so they should be the default. Count-Min earns its place only when you need point queries for arbitrary items rather than just the top ones. As Count-Min showed, those point queries are trustworthy only for the heavy items anyway, which narrows its advantage a lot.

Both are mergeable. Neither is idempotent.