Neural Sync Active

HyperLogLog

Registry Synced

96 words

1 min read

Reading compass

Now · The Distinct Counting Problem

The Distinct Counting Problem

Given a stream of elements, count the number of distinct elements using minimal memory. Trivial solution: Keep a hash set —

O(n)

memory. HyperLogLog:

O(\log \log n)

memory,

1-2\%

accuracy.

Hash each element to a uniform binary string
Find the position $r$ of the leftmost 1-bit
Track the maximum $r$ across all elements: $R$
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