Count-Min & HyperLogLog
In short: a count-min sketch counts occurrences of many keys in a fixed
d × w grid instead of one counter per key. Every event increments one
cell per row — a different column in each row, picked by a different hash
function. A query reads all d of a key's cells and reports the minimum,
because a cell can only be inflated by collisions with other keys, never
deflated: the smallest cell is always the closest to the truth, and the
estimate is never below the real count. HyperLogLog answers a different
question — not "how many of X" but "how many distinct keys overall" —
using the same "give up exactness, buy back memory" trade: it tracks the
longest run of leading zero bits seen per bucket, because seeing a long run
of zeros is rare enough that it implies a lot of distinct hashes were tried.
Count events by key without a dict per key
Quarry's live dashboard tracks how often each of millions of possible event types fires, in bounded memory:
With only 4 columns per row, "dog" and "fox" collide in row 0, and
"cat" and "fox" collide in row 1 — so "fox"'s two cells are 2 and
3, and its estimate comes out as min(2, 3) = 2, one more than its true
count of 1. "dog" still reads correctly at 1, because row 1's cell for
"dog" wasn't shared with anything. More rows means more independent
chances to dodge a collision — that's the entire reason count-min uses more
than one hash function.
Note the hash: Python's own hash() changes between runs unless
PYTHONHASHSEED is fixed (see the Bloom filters lesson), so this uses
hashlib.md5 keyed on a seed string instead — fully reproducible, on any
machine, forever.
Watch the grid fill as 4 events arrive, then see the query take the min:
Each event lights one cell per row. Querying a key takes the MIN across its d cells — collisions can only push an estimate up, never down.
Event 1, "cat", lights row 0 col 2 and row 1 col 2. 2 by 4 table. 8 of 8 cells filled.
How many distinct visitors, without a set of them all
Counting distinct keys with a set() costs memory proportional to how
many distinct keys there are. HyperLogLog trades exactness for a handful of
small registers: hash each item, use its first few bits to pick a register,
and in that register keep the longest run of leading zeros seen in the
rest of the hash — because getting a hash with many leading zeros is
exponentially rare, and seeing one at all is evidence that many distinct
items have been tried:
A register holding 5 means "the longest zero-run assigned to this bucket
was 5 bits" — rare for a small stream, likely once thousands of distinct
items have passed through. Averaging that signal across many registers (the
hll_registers / estimate_cardinality exercises below) turns it into a
cardinality estimate using a small, fixed amount of memory regardless of
whether a million items or a billion passed through.
Quick practice
def leading_zero_bits(h, width):
if h == 0:
return width
count = 0
bit = 1 << (width - 1)
while bit and not (h & bit):
count += 1
bit >>= 1
return count
print(leading_zero_bits(0, 4), leading_zero_bits(0b1111, 4))d, w = 3, 100
print(d * w < 100 * 100)🎯 Your turn
Build count_min_estimate(events, queries, d, w, seed): build a d x w
counter grid, increment one cell per row for every event in events (using
_hash_to_row), then return a dict mapping each key in queries to the
minimum of its d cells.
count_min_estimate(["cat","cat","dog","fox"], ["cat","dog","fox"], d=2, w=4, seed=5)→{"cat": 2, "dog": 1, "fox": 2}
Hint: table = [[0] * w for _ in range(d)]. For each event, increment
table[r][_hash_to_row(event, r, seed, w)] for every row r. Each query's
answer is min(table[r][_hash_to_row(query, r, seed, w)] for r in range(d)).
Press ▶ Run, try the Live App chips, then ✓ Check.