You have a stream of billions of events — API calls, ad clicks, DNS queries, cache keys — and you want to know which few are responsible for most of the traffic. You can't sort. You can't keep a counter per item. The set of distinct keys is too big for memory. This is the heavy hitters problem: find every item that appears more than φN times in a stream of length N, using memory that doesn't grow with the number of distinct keys.

The naive approach — hash map of counters — dies when your key space is 100M unique URLs. Top-K sketches (like Count-Min + a heap) give you approximate top-N but can miss items that were briefly hot then went cold. Heavy hitters is a stricter question: which items exceeded a threshold at all?

The Misra-Gries algorithm is the classic answer. Keep k counter slots (where k = 1/φ). For each incoming item:

• If it's already in a slot, increment its counter.
• If there's a free slot, put it there with count 1.
• Otherwise, decrement every counter by 1. Any that hit zero become free.

That decrement-everything step is the trick. It's O(k), not O(N). And it guarantees: any item that truly appears more than N/k times will still be in the table at the end. False positives are possible; false negatives are not. You then do a second pass (or use exact counters alongside) to verify the candidates.

Real-world example: Cloudflare and Fastly use heavy hitters variants to detect DDoS-style traffic patterns and hot cache keys. Suppose you're processing 10B DNS queries/day and want to find every domain queried more than 0.01% of the time. That's φ = 0.0001, so k = 10,000 counters. Ten thousand slots — a few hundred KB of memory — instead of tracking hundreds of millions of distinct domains. When a domain suddenly spikes (botnet C2, viral link, misconfigured client), it shows up in the table within seconds.

Rule of thumb: to find items above frequency φ, you need k = ⌈1/φ⌉ counters for Misra-Gries. Want everything above 1%? 100 slots. Above 0.1%? 1,000 slots. Memory is inversely proportional to the threshold, independent of stream size or key cardinality.

The variant you'll see in production is Space-Saving (Metwally et al.), which is similar but tracks an "error" per counter so you get tight bounds on the actual frequency, not just membership. Redis's TOPK command uses it under the hood.

Don't reach for exact counts when approximate answers are cheaper by four orders of magnitude and just as actionable.