Heavy Hitters & Frequent Items

Finding the Few Keys That Dominate

Imagine counting votes on a board with room for only a few names. If Alice appears repeatedly, her name should survive even while thousands of one-off names arrive. A heavy hitter is a key whose frequency exceeds a specified share of the stream; a candidate is a key retained for later checking. For the stream A, B, A, C, A, B, D, A, the frequency of A is 4 of 8, B is 2 of 8, and C and D occur once. At a threshold strictly above 1/4, A qualifies; B is exactly on the boundary and does not. Which names can we guarantee to keep with limited counters? What happens when an attacker spreads traffic across many keys? These questions connect point-frequency estimates from the previous chapter to a harder task: discovering which keys to query at all. A point query answers a supplied key; it does not enumerate the unknown keys. In telemetry and search logs, the universe of possible keys can dwarf the memory budget.

Thresholds, Tails and Candidate Sets

Let an insertion-only stream contain $N$ unit updates over universe $U$, with nonnegative frequencies $f_x$ and $\lVert f\rVert_1=N$. For $0<\phi<1$, an $\ell_1$ heavy hitter satisfies $f_x>\phi N$. There are fewer than $1/\phi$ such keys, but identifying them requires a candidate mechanism. An $\ell_2$ heavy hitter instead satisfies $f_x>\phi\lVert f\rVert_2$, where $\lVert f\rVert_2=(\sum_x f_x^2)^{1/2}$; the two threshold scales differ. A useful approximate reporting contract has an inclusion threshold $\phi N$ and an exclusion threshold $(\phi-\varepsilon)N$: include every key strictly above the first, exclude every key strictly below the second, and permit either decision inside the gap. This gap is necessary when frequencies have additive error $\varepsilon N$. A top-$k$ query asks for the $k$ largest frequencies, which does not imply a particular absolute threshold; ties require an explicit policy. With $m=\lceil1/\varepsilon\rceil-1$ counters, Misra–Gries retains every key with $f_x>\varepsilon N$ under unit insertions. This is a recall statement, not an exact-frequency statement. Space-Saving retains keys using a different replacement rule and upper estimates; its bounds also assume nonnegative unit arrivals.

flowchart TD
  A["Unit insertions; nonnegative counts"] --> B["N equals total updates"]
  B --> C["MG: at most N/(m+1) cancellations"]
  C --> D["All keys above N/(m+1) retained"]
  D --> E["Verify candidates for reporting"]
  A --> F["L2 norm defines another threshold"]
  classDef navy fill:#17365D,color:#fff
  classDef teal fill:#147D84,color:#fff
  classDef crimson fill:#C6284D,color:#fff
  classDef purple fill:#6C3BAA,color:#fff
  class A,B navy
  class C,D teal
  class E crimson
  class F purple

Why Frequent-Item Guarantees Differ

The key accounting idea is cancellation. Misra–Gries either increments an existing key, opens a free counter, or decrements all $m$ stored counters when a new key arrives and all counters are occupied. Each decrement can be charged to a group of $m+1$ distinct stream occurrences: the incoming occurrence plus one occurrence represented by each counter. If there are $D$ global decrement rounds, $(m+1)D\leq N$. For every key, its final stored counter (zero if absent) lies between $f_x-D$ and $f_x$. Hence an absent key has $f_x\leq D\leq N/(m+1)$, proving the candidate guarantee. The proof uses positive unit arrivals and distinct occupied keys. For weighted positive updates, a unit expansion or properly weighted variant is needed; for deletions, cancellation cannot simply reuse this invariant. Space-Saving replaces a minimum counter of value $c$ with the new key and value $c+1$, retaining an error field $c$: an existing key's true frequency lies between estimated count minus error and estimated count. The minimum counter and bounded error support candidate recall, but neither method certifies exact ranks from its counters alone. A second pass can count the survivors exactly; otherwise pair with a point-query sketch and account for its own error and probability.

flowchart TD
  A["Unit insertions"] --> B["Every decrement charges m+1 distinct occurrences"]
  B --> C["D at most N/(m+1)"]
  C --> D["Absent key count at most D"]
  D --> E["Above threshold implies retained"]
  A --> F["Deletion or incompatible weights"]
  F --> G["Cancellation proof fails"]
  classDef navy fill:#17365D,color:#fff
  classDef teal fill:#147D84,color:#fff
  classDef crimson fill:#C6284D,color:#fff
  classDef purple fill:#6C3BAA,color:#fff
  class A,B navy
  class C,D teal
  class E purple
  class F,G crimson

Hot Shards, Trending Terms and Attack Traffic

For a small website, count product clicks in a rolling batch to locate popular products; one key per click and a fixed reporting interval make the insertion model credible. At production scale, a router might process $10^8$ requests per minute across millions of customer IDs with room for only a few hundred counters per shard. Define whether the objective is per-shard or global heavy hitters: a key spread across shards can be globally heavy without qualifying locally. Candidate sets from all shards may be unioned and verified against merged frequency summaries or exact logs, subject to their error budgets and merge rules. For attack traffic, a bot can rotate identities so no single ID exceeds the threshold even while one source controls substantial volume. The mathematical guarantee is still valid for the chosen key, but its operational interpretation fails; aggregate by an appropriate trusted identity or combine with other signals. Window expiry and deletions also invalidate insertion-only proofs unless the system rebuilds per window or uses a compatible turnstile/windowed method.

Build a Heavy-Hitter Decision Rule

Choose a signal, key, time horizon, threshold and allowable uncertainty before selecting a summary. Start from a desired guarantee: full recall above $\phi N$, no reports below $(\phi-\varepsilon)N$, or a ranked top-$k$ with an explicit tie rule. Compute the memory implied by candidate generation, then budget verification error separately. Compare exact counts on a small trace, stress boundary cases, and document whether updates can be negative or adversarial. The exercises below turn those decisions into reproducible artifacts. The frequency-estimation prerequisite explains why a sketch can verify nominated keys but cannot by itself discover arbitrary names; the next useful bridge is frequency moments and norms, whose $\ell_2$ scale changes what “heavy” means.