HyperLogLog From Scratch | Counting Distinct Elements at Scale

How HyperLogLog estimates the number of distinct elements in massive data streams. HyperLogLog Paper: P. Flajolet, É. Fusy, O. Gandouet, and F. Meunier, “HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm,” Discrete Mathematics & Theoretical Computer Science, Proc., 2007. One thing I didn’t explain in the video: When you split data across HyperLogLog registers/computers, each register sees fewer elements. You might worry this makes each estimate noisier, which could counteract how averaging reduces variance. In practice, averaging still helps because when the registers are balanced (roughly the same number of elements), the variance of each scaled estimate stays about the same as if we hadn’t sharded (split the data into registers/computers). Since the variance doesn’t blow up, averaging effectively reduces the overall noise. .................................................................................... 00:00 - Naïve Counting Algorithm 01:55 - Simple Case: Counting Numbers 03:18 - Extension: Counting Other Things 05:50 - Efficiency: Tracking Longest Run of Zeros 08:02 - Stabilization: Averaging for Stabilization 10:15 - Routing Bitstrings 10:50 - The Algorithm 12:20 - Why “HyperLogLog”? 12:50 - Practical Details