Estimator

At this point, we have many registers, each running a tiny version of the original “single-counter” experiment. What remains is to combine them into one final estimate.

N = \alpha\,m^2\left(\sum_{i=1}^{m} 2^{-M[i]}\right)^{-1}

$m$ is the number of registers
$M[i]$ is the value in register $i$
$\alpha$ is a small correction constant

Correction constant

Even after proper scaling, the estimator has a small, systematic bias that depends only on m. This is corrected by a constant α.

m	α
16	0.673
32	0.697
64	0.709
≥ 128	0.7213 / (1 + 1.079 / m)

Implementation

Here’s the estimation code that combines all registers into a single cardinality estimate:

function getAlpha(m: number): number {
  if (m === 16) return 0.673;
  if (m === 32) return 0.697;
  if (m === 64) return 0.709;
  return 0.7213 / (1 + 1.079 / m);
}
 
class HyperLogLog {
  // ... constructor and add() method from before ...
 
  estimate(): number {
    const m = this.m;
    const alpha = getAlpha(m);
 
    // Sum 2^(-M[i]) for all registers
    let sum = 0;
    for (let i = 0; i < m; i++) {
      sum += Math.pow(2, -this.registers[i]);
    }
 
    // Apply the harmonic mean formula
    return (alpha * m * m) / sum;
  }
}

Multiple Counters Low Cardinality