Probabilistic structures
Heavy-Hitter Hot Window
Estimate the top talkers in a million-event firehose with four tiny counter rows.
How to read this lab
A Count-Min Sketch estimates how many times each key has appeared using only a few tiny counter rows — far less memory than tracking every key exactly. Its estimate can only ever be too HIGH, never too low, and you can watch exactly why by inspecting which other keys are colliding into the same counters.
Controls
- Width w (columns)
- How many counters each hash row has. Narrower means more keys collide into the same counter, so estimates get less accurate — wider fixes it, at the cost of more memory.
- Stream volume
- How many events are fed into the sketch per animation frame — a faster or slower firehose.
- Pause stream / Resume stream
- Freezes the firehose so you can inspect the current state.
What to watch for
- Query any key — its estimate is always greater than or equal to its true count, never less. That's not a coincidence, it's a hard guarantee.
- Narrow Width w down and watch Total overest. error climb — more collisions, worse estimates.
- Widen it back up and the error shrinks for the exact same stream.
- Open the collision autopsy to see the real other keys stacking onto your selected key's counter — the overestimate isn't mysterious, it's literally those keys' counts leaking in.
Why it happens
Each row increments a counter by hashing the key to a column — if two different keys hash to the same column, they share (and inflate) that counter. The sketch takes the MINIMUM across all rows as its estimate, because a key's true count can never be reduced by a collision, only inflated, so the row where it collided least gives the tightest (but still never-too-low) estimate. More columns means fewer collisions per row, which is why widening the sketch directly reduces the total overestimation error — the same width/accuracy tradeoff every production Count-Min Sketch, used in real systems like Redis and network traffic monitors for finding heavy hitters, has to tune.
Try this first — Query one of the leaderboard's top keys, note its estimate vs true count, then open the collision autopsy for a row and see who else is sharing its cell.
Warming up…
The firehose just (re)started — give it a moment to fill the counter grid before reading the estimates below.
- Counter heat (higher = hotter)
- Selected key — cell hit this row
- Row giving the MIN (the estimate)
Query
Estimate a key
Pick a key to highlight its cell in every row and see which row produces the minimum (the sketch's reported estimate).
Sketch shape
Depth is fixed at 4 independent hash rows. Narrower width means more collisions per column and more overestimation; widening it rebuilds the sketch fresh.
Firehose
Events processed
0
Distinct keys
0
Total overest. error
0
Sum over all keys of estimate - truth
Grid size
4×64
depth × width
Leaderboard
Top estimated heavy hitters
Waiting for events to stream in…