Back to Sandbox

Data Sketch

Counting the uncountable with HyperLogLog. Stream millions of events through a few kilobytes of registers and watch the estimate chase the true distinct count.

View source
True distinct
0
0 events seen
HLL estimate
0
0% of registers used
Error
+0.00%
theory ±0.00%
Memory
12.0 KB
16,384 registers
p=14 · 16,384 registers · 12.0 KB · ±0.81%
≈ 300,000 / sec
Space StreamU +1M uniqueD +1M duplicatesR Reset

About this experiment

HyperLogLog answers one question — “how many distinct things have I seen?” — without storing the things. Each incoming key is hashed; the leading bits pick one of 2 ᵖ registers, and each register remembers only the longest run of leading zeros it has witnessed. Rare long runs imply many distinct inputs, so a harmonic mean over the registers recovers the count. The memory never grows with the data: every readout above comes from the same 16,384 one-byte registers, whether you feed it ten items or ten million.

Slide precision up for more registers and a tighter error band; slide it down to watch the estimate get noisy. Hit +1M duplicates to confirm the payoff: the event counter rockets while the estimate barely twitches, because duplicates carry no new information. That is the whole trick behind APPROX_COUNT_DISTINCT, Redis PFCOUNT, and ClickHouse uniq — a defensible number with a known error bound, computed in one pass over a firehose.