HyperLogLog

The add operation consists of computing the hash of the input data v with a hash function h, getting the first b bits (where b is ${\textstyle \log _{2}(m)}$), and adding 1 to them to obtain the address of the register to modify. With the remaining bits compute ${\textstyle \rho (w)}$ which returns the position of the leftmost 1. The new value of the register will be the maximum between the current value of the register and ${\textstyle \rho (w)}$.

${\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b}\rangle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j],\rho (w))\\\end{aligned}}}$

The count algorithm consists in computing the harmonic mean of the m registers, and using a constant to derive an estimate ${\textstyle E}$ of the count:

${\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}$

${\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}}$

${\displaystyle E=\alpha _{m}m^{2}Z}$

The intuition is that n being the unknown cardinality of M, each subset ${\textstyle M_{j}}$ will have ${\textstyle n/m}$ elements. Then ${\textstyle \max _{x\in M_{j}}\rho (x)}$ should be close to ${\textstyle \log _{2}(n/m)}$. The harmonic mean of 2 to these quantities is ${\textstyle mZ}$ which should be near ${\textstyle n/m}$. Thus, ${\textstyle m^{2}Z}$ should be n approximately.

Finally, the constant ${\textstyle \alpha _{m}}$ is introduced to correct a systematic multiplicative bias present in ${\textstyle m^{2}Z}$ due to hash collisions.

The constant ${\textstyle \alpha _{m}}$ is not simple to calculate, and can be approximated with the formula[1]

${\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{\text{for }}m=16;\\0.697,&{\text{for }}m=32;\\0.709,&{\text{for }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{for }}m\geq 128.\end{cases}}}$

The HyperLogLog technique, though, is biased for small cardinalities below a threshold of ${\textstyle {\frac {5}{2}}m}$. The original paper proposes using a different algorithm for small cardinalities known as Linear Counting.[5] In the case where the estimate provided above is less than the threshold ${\textstyle E<{\frac {5}{2}}m}$, the alternative calculation can be used:

1. Let ${\textstyle V}$ be the count of registers equal to 0.
2. If ${\textstyle V=0}$, use the standard HyperLogLog estimator ${\textstyle E}$ above.
3. Otherwise, use Linear Counting: ${\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}$

Additionally, for very large cardinalities approaching the limit of the size of the registers (${\textstyle E>{\frac {2^{32}}{30}}}$ for 32-bit registers), the cardinality can be estimated with:

${\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}}\right)}$

With the above corrections for lower and upper bounds, the error can be estimated as ${\textstyle \sigma =1.04/{\sqrt {m}}}$.

The merge operation for two HLLs (${\textstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2}}$) consists in obtaining the maximum for each pair of registers ${\textstyle j:1..m}$

${\displaystyle {\mathit {hll}}_{\text{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}$