Count-Min Sketch and Heavy Hitters
Count-Min Sketch estimates item frequency using compact counter arrays; collisions make its basic estimates overestimate nonnegative frequencies.
Count-Min Sketch and Heavy Hitters
Count-Min Sketch estimates item frequency using compact counter arrays; collisions make its basic estimates overestimate nonnegative frequencies. For each item, update one counter in each of d rows using independent hashes. Estimate frequency by taking the minimum selected counter. Common parameter choices use width w≈e/ε and depth d≈ln(1/δ). The sketch does not identify candidate keys by itself; retain candidates separately.
Mechanism and worked example
A gateway estimates request frequency by API key using a fixed counter matrix. Collisions add unrelated traffic to counters, biasing estimates upward. Candidate tracking can use a heap or Space-Saving summary and verify top candidates against a larger window.
| Structure | Question answered | Limitation |
|---|---|---|
| Count-Min | How frequent is key x? | Overestimates under collisions |
| HyperLogLog | How many distinct keys? | No identities |
| Bloom filter | Could key x be present? | Positive may be false |
| Quantile sketch | Approximate p95/p99? | Rank/value error |
Failure modes and operations
Counter overflow, inconsistent hash seeds, negative updates and poor candidate retention can invalidate assumptions. Basic nonnegative Count-Min does not enumerate keys. Merging requires compatible dimensions, seeds and update semantics.
Trade-offs and design boundary
Count-Min is compact for point-frequency estimates but cannot list keys or estimate distinct counts. Exact counters are simpler at moderate cardinality. Heavy-hitter algorithms trade candidate precision and update cost differently.
Interview transfer exercise
Design top-endpoint detection. Retain candidate identities separately and periodically verify against source data; a Count-Min matrix alone cannot enumerate the top endpoints.
Read the diagram
Hash item into one counter per row → Increment selected counters → Query returns minimum selected counter → Candidate tracker retains possible heavy hitters