HyperLogLog

The Distinct Counting Problem

Algorithm

1. Hash each element to a uniform binary string
2. Find the position $r$ of the leftmost 1-bit
3. Track the maximum $r$ across all elements: $R$
4. Estimate: $n \approx \alpha_m m \cdot 2^{\bar{R}}$ Where $m$ is the number of registers (typically $2^{14} = 16384$), $\alpha_m$ is a bias correction constant. Join Discord PreviousStreaming AlgorithmsNextRandomized Optimization