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
α 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:

class HyperLogLog {
  // ... constructor and add() method from before ...
 
  estimate(): number {
    const m = this.m;
 
    // Choose the correction constant based on m
    const alpha =
      m === 16
        ? 0.673
        : m === 32
          ? 0.697
          : m === 64
            ? 0.709
            : 0.7213 / (1 + 1.079 / 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
    const E = (alpha * m * m) / sum;
 
    return E;
  }
}

Multiple Counters Low Cardinality