HyperLogLog

Cardinality estimation in tiny memory — hash, pick a register by prefix, count leading zeros, estimate from the harmonic mean

add: O(1) count: O(m) memory: O(m) ≈ fixed error ≈ 1.04/√m

Controls

p=4 slowfast
index bits (first p) leading zero first one target register register updated

Step 1–3: hash item → prefix picks register → count leading zeros of the rest

Add an item to see its hash decomposed.

Step 4: registers fill with the MAX rank per bucket (16 registers)

Step 5: estimate from the harmonic mean vs the true count

True distinct
0
HLL estimate
0
Relative error
0%
Empty registers (V)
16
Method
—

Accuracy table: error ≈ 1.04/√m (independent of n)

pm = 2^p1.04/√mdense memory (6-bit)

Operation Log