Loading page…
Count every key in fixed memory with a Count-Min sketch sized from (ε, δ), never undercount, and keep a top-k of the hottest keys as the stream goes by.
Before you can fix a hot key you have to find it, and counting every key exactly costs memory in proportion to the number of keys (Day 4, section 2.1, Approach 1). A Count-Min sketch (Approach 2) counts in fixed memory: a grid of depth rows × width counters. Each key bumps one counter in every row; its estimate is the smallest of those counters. Other keys landing on the same counters can only add, so the estimate never undercounts: a key that crossed your hot threshold is always reported (no false negatives), while a warm key may look hot (false positives).
1. CountMinSketch(width, depth, hasher=hash_pair)
| Member | Does |
|---|---|
add(key, count=1) |
adds count to the key's counter in every row; ValueError for a negative count |
estimate(key) |
the minimum of the key's counters (an int) |
total |
the sum of every count added so far (N) |
CountMinSketch.for_error(epsilon, delta, hasher=hash_pair) |
a sketch sized for "overestimate by at most epsilon × N, with probability at least 1 − delta": width = ceil(e / epsilon), depth = ceil(ln(1 / delta)). ValueError unless both are strictly between 0 and 1 |
Row i's counter for a key is column (h1 + i * h2) % width, where (h1, h2) = hasher(key) (given: two FNV-1a hashes). Use exactly that rule; the tests depend on it.
2. HeavyHitters(sketch, k): the top k keys of a stream.
| Method | Does |
|---|---|
record(key, count=1) |
adds to the sketch, then updates the candidates, and returns the key's new estimate |
top(n=None) |
up to n (default: all) candidates as (key, estimate) pairs, highest estimate first, ties by key ascending |
Keep at most k candidates with their latest estimates. After recording key: if it's already a candidate, store its new estimate; else if there are fewer than k, add it; else if its estimate is greater than the smallest candidate's (ties: the smallest key name goes first), replace that one.
In JavaScript and TypeScript: new CountMinSketch(width, depth, hasher = hashPair) with add, estimate, the total property and the static CountMinSketch.forError(epsilon, delta, hasher = hashPair); new HeavyHitters(sketch, k) with record(key, count = 1) and top(n), which returns [key, estimate] arrays. Errors are thrown as RangeError.
Cormode and Muthukrishnan, who introduced the sketch ("An Improved Data Stream Summary: The Count-Min Sketch and its Applications", 2005), prove that with width = ⌈e/ε⌉ and depth = ⌈ln(1/δ)⌉ an estimate exceeds the true count by more than ε·N with probability at most δ. The lesson's 10,000 × 7 grid is ε ≈ 0.00027 and δ ≈ 0.0009. The paper uses an independent hash function per row; deriving every row from two hashes, h1 + i·h2, is a common shortcut (Kirsch and Mitzenmacher analysed it for Bloom filters).
Write your code, then run 3 example tests and 10 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and the runtime restarts, your code stays.