Build a HyperLogLog

leading-zero ranks per register

Challenge 4 of Probabilistic StructuresAdvanced~60 min

Estimate how many DISTINCT items a stream has seen using a few kilobytes instead of storing them all. Derive a bucket and rank from a hash, keep the max rank per bucket, turn the registers into a cardinality estimate, correct the small-range bias, and merge sketches, the count-distinct engine behind Redis PFCOUNT and analytics at scale.

5 steps

1. 1Bucket and Rank
2. 2Adding Items
3. 3The Raw Estimate
4. 4Small-Range Correction
5. 5Merging Sketches