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
Design top-endpoint detection. Retain candidate identities separately and periodically verify against source data; a Count-Min matrix alone cannot enumerate the top endpoints.
Your design draft
Clarify assumptions, explain your approach, and test the difficult cases. Save your draft, then compare it with the study notes.
Self-review checklist
Self-guided practice. Automated AI feedback and code execution are not connected.