Misra-Gries heavy hitters
/ MISS-ruh GREES /
Suppose a billion votes stream past you and you must name every candidate who got more than, say, 1% of them — but you can only afford to track a handful of tallies, nowhere near one per candidate. How can you find the truly popular items without remembering everyone? Misra-Gries is the elegant answer: a tiny set of counters that, in one pass and almost no memory, is guaranteed to catch every 'heavy hitter' (any item whose frequency exceeds a chosen threshold), while never reporting an item that was actually rare by much.
The algorithm keeps at most k-1 (item, count) pairs and follows three rules per arriving item x. If x already has a counter, increment it. Else if fewer than k-1 counters are in use, start a new counter for x at 1. Else (all counters busy and x is new), decrement EVERY counter by 1, deleting any that hit 0. That last rule is the clever heart: think of it as cancelling out k different items at once, like pairing off opposing votes. The guarantee that follows: each counter's value undercounts the true frequency by at most m/k, where m is the stream length. So any item appearing more than m/k times survives with a positive count and is reported. With k around 1/epsilon, every item with frequency above epsilon*m is found, using only O(1/epsilon) counters. It is a one-sided estimate: it may slightly undercount, never overcount.
Misra-Gries matters because heavy hitters are everywhere worth finding: the busiest IP addresses flooding a network, the trending search terms, the best-selling products, the most frequent error codes — all detectable in a single sweep with kilobytes of state. It generalizes the classic Boyer-Moore majority trick (which finds an item appearing more than half the time using ONE counter) to any threshold. The honest caveats: the counts are lower bounds (true frequency is between the stored count and count + m/k), it finds candidate heavy hitters but a second pass may be needed to verify exact frequencies, and it tells you which items MIGHT be heavy, guaranteeing it never misses a real heavy hitter but possibly listing a few borderline ones.
Stream A,A,B,C,A,B,A with k=3 (keep 2 counters). A->{A:1}; A->{A:2}; B->{A:2,B:1}; C is new and both counters busy, so decrement all: {A:1} (B drops to 0, removed); A->{A:2}; B->{A:2,B:1}; A->{A:3}. A is reported; its stored count 3 undercounts the true 4 by at most m/k = 7/3.
k-1 counters; decrement all on overflow. Catches every item above m/k, undercounting by <= m/k.
Misra-Gries counts are LOWER bounds: true frequency lies in [stored count, stored count + m/k]. It never misses a genuine heavy hitter but may list a few false positives, so exact frequencies often need a verification pass. It is the multi-counter generalization of the Boyer-Moore majority vote.