How accurate is HyperLogLog for counting unique visitors?

At one million unique visitors, a 16,384-register HyperLogLog was off by 0.754% RMSE across 30 seeded trials, slightly better than the 0.81% everyone quotes. That result is not where you should worry. HyperLogLog accuracy depends on two other things. The first is where your visitor count sits: the same sketch was 2.604% off at 40,960 visitors, and every one of those 30 trials overcounted. The second is the hash. With 64-bit FNV-1a on sequential IDs like user_1234567, it reported one million visitors as about 105,000 on average, an undercount of 89.5% (calculated from the mean error).

The quoted figure comes from the standard error formula 1.04/sqrt(m), where m is the number of registers. It is what Redis PFCOUNT, the Postgres hll extension and BigQuery's APPROX_COUNT_DISTINCT family trade on. I wanted to know whether it holds at the counts a small product actually has, from ten visitors a day to ten million a year.

Hardware: Apple M3, 16 GB, macOS 26.4.1, Node v23.5.0. No packages. Other benchmarks were running on the same machine, so timings are medians and I lean on ratios. Accuracy numbers do not depend on load. Every run is seeded.

The short answer

• The formula holds at scale. With p = 14 (16,384 one-byte registers) the measured RMSE was 0.699% at 100,000 visitors, 0.754% at 1,000,000 and 0.847% at 10,000,000, against a predicted 0.813%. Mean bias stayed within ±0.2%.
• The worst place is the hand-off, not small counts. Below 2.5m the sketch uses linear counting, which is very accurate: 0.031% at 10 visitors and 0.622% at 100. Just past the switch, the raw estimator runs 2.5% high: 2.604% RMSE at 40,960 visitors (p = 14), and 2.998% at 10,000 for p = 12.
• The hash can wreck it without any error. 64-bit FNV-1a on sequential user_<n> IDs gave −89.5%. Java's hashCode gave −99.98%. The same FNV-1a plus a MurmurHash3 fmix64 finalizer gave 0.978%. On random UUIDs, every hash I tried was fine.
• Merging is exact; intersecting is not. Merging two sketches, each register taking the larger value, gave registers identical to one sketch built over the union in 60 of 60 trials. Intersection by inclusion-exclusion had two to two and a half times the error: 1.571% RMSE on a 500,000-visitor overlap.
• Memory is the reason to use it; speed is not. 16,384 bytes of registers against 77,026,592 bytes for a Set of one million UUID strings (4,701x, calculated). Per add, both cost 103-113 ns.

How was the HyperLogLog built?

One construction, stated exactly. The hash is 64 bits, made from two MurmurHash3 x86_32 calls: the second is seeded with the first. The top p bits choose a register. The register keeps the maximum of "leading zeros in the remaining bits, plus one". The estimate is the textbook one:

raw = alpha * m * m / sum(2 ** -register[j]);      // alpha = 0.7213 / (1 + 1.079/m)
if (raw <= 2.5 * m && zeros > 0) return m * Math.log(m / zeros);   // linear counting
return raw;

With 64-bit hashes you do not need the large-range correction from the original paper. Visitor IDs are 36-character UUID v4 strings from a seeded PRNG. The first 32 bits are a bijection of the index, so IDs never repeat; a Set of a million of them confirmed it.

Does the 0.81% standard error hold?

Thirty independent trials per cell, each with a different seed, all three precisions fed from the same stream.

Once the count is well past the register count, measured RMSE sits between 21% below and 4% above 1.04/sqrt(m) at every precision. Thirty trials cannot resolve a closer match, so treat the formula as correct. At p = 14 the worst single trial was 2.1 to 2.6 times the RMSE. At p = 10, one trial of a million missed by 11.94%. If you quote a dashboard number, give a range two or three standard errors wide.

The 10-visitor row is really about integers. At p = 10 and 12 the RMSE is 1.8% because one trial in 30 counted 9 visitors instead of 10: two IDs shared a register. That kind of error is one visitor.

The row to look at is p = 12 at 10,000 visitors: 2.998%, 1.8 times the quoted figure, with a +1.77% bias. Ten thousand is an ordinary monthly count. It sits at 2.44m, just where the sketch stops using linear counting.

Where does HyperLogLog go wrong at small counts?

I expected small counts to be the weak spot. They are not. Linear counting just counts empty registers, and it is excellent while most registers are empty. The raw HLL estimator, on its own, is useless down there. Without the correction, p = 14 reported +1,130% at 1,000 visitors and +73% at 10,000.

The trouble is the threshold. At 2.5m the code switches from an estimator that is still accurate to one that is still biased. Here is p = 14, 30 trials, each estimator computed at the same points:

The error triples at the switch. All 30 trials overcounted, and the smallest error was +0.974%, and it takes until about 4m for the raw estimator to settle. Moving the threshold from 2.5m to about 3.5m would have cut the worst error in this range from 2.60% to about 1.24%, since linear counting measured 1.24% at 3.5m. That figure comes from this table, not from a separate test. p = 12 showed the same shape: 2.82% at 2.5m.

This bump is what HyperLogLog++ corrects with its empirical bias tables, and what Otmar Ertl's estimator removes analytically. I did not run Redis, Postgres or BigQuery here, so I cannot say how they behave. If you wrote your own sketch from the 2007 paper, or use a small library that did, check whether your counts sit between 2.5m and 4m. For p = 14 that is 41,000 to 65,000 visitors.

Does the hash function matter for HyperLogLog?

On random UUIDs, barely. On sequential IDs, it decides whether the answer means anything. p = 14, one million visitors, 30 trials:

FNV-1a is a fine hash for hash tables, and random UUIDs hid its weakness completely. I expected the failure to be registers that never get used. It was not. On user_9064501 through user_10064500, FNV-1a indexed 16,335 of the 16,384 registers. The damage was in the values stored. The average register held 4.47, where MurmurHash3 held 7.28. The most common value was 3, against 7 for MurmurHash3, and the sketch estimated 109,514. The IDs differ only in their last few digits, and FNV-1a mixes each character in with a single multiply by 2^40 + 435. So the bits that pick the register and the bits that set its value move together. Each register ends up behaving as if it saw about a tenth of the visitors. hashCode is worse: its 32-bit multiply-by-31 gives neighbouring IDs neighbouring hashes, and all million IDs landed in just 207 registers.

The sketch did not warn about any of this. It returned a smooth, plausible, wrong number, which is the same silent failure as a Bloom filter with a weak hash. A 64-bit finalizer fixes it, and costs three multiplies. The cheap test: feed sequential IDs into the sketch and compare with an exact count once.

How much memory does HyperLogLog save over a Set?

Measured in separate processes with --expose-gc: a forced GC before and after, keeping only the structure alive.

The 16,384 is the measured arrayBuffers growth at every size. The heap also grew by 78-84 KB, but a control process that built and discarded the same sketch grew by 81-100 KB. That growth is compiled code, not data. Redis stores the same 16,384 registers in 6 bits each, which is where "12 KB" comes from: 16,384 × 6 / 8 = 12,288 bytes (calculated). p = 12 fits in 4,096 bytes at twice the error.

Below about 10,000 visitors the saving is under a megabyte, and an exact COUNT(DISTINCT) is often simpler. The case for a sketch is one per page, per day and per customer, where there are thousands of counters. The same trade, a few bytes standing in for a lot of data, is behind MinHash deduplication. What an exact COUNT costs in Postgres covers the other side.

Can you merge HyperLogLog sketches?

Yes, and the union loses nothing. Two sketches A and B of N visitors each, half of them shared, p = 14, 30 trials each:

In all 60 trials, the merged registers matched a sketch built directly over the union, byte for byte. Weekly uniques from daily sketches are exactly as good as counting the week in one go.

Intersections are a different matter. Inclusion-exclusion subtracts three noisy estimates. At 50% overlap that already doubles the relative error. Smaller overlaps will be worse, because the absolute error stays at the size of the union while the thing you are measuring shrinks. I only measured 50%. The answer to "how many visitors came both days" is the weakest number a sketch gives.

Is HyperLogLog faster than a Set?

No, and it does not need to be. Median of nine timed runs over one million pre-built UUIDs, one process per structure, two rounds:

An add is two passes of MurmurHash3 over 36 characters, and that costs about the same as the Set hashing the string once and storing it. A p = 14 estimate takes half a millisecond with my plain 2 ** -r loop. It is fine per request, but a lookup table is the obvious fix if you read thousands of counters. The memory numbers are the reason to use one.

Check it yourself

One file, no dependencies, Node 18 or newer, about 16 seconds here. It reproduces the three headline numbers: the 0.754% at one million, the 2.604% at the switch, and the FNV-1a collapse. Save it as hll-check.cjs; the .cjs extension keeps it CommonJS inside an ESM project.

node hll-check.cjs

Output on this machine:

node v23.5.0  p=14  m=16384 registers (16384 bytes)  trials=30
quoted standard error 1.04/sqrt(m) = 0.813%

UUID visitor IDs, MurmurHash3 x2 (64-bit):
  n = 1,000,000   RMSE 0.754%  mean -0.011%  worst 1.705%
  n =    40,960   RMSE 2.604%  mean 2.539%  worst 3.681%   <- just past the 2.5m switch to the raw estimator

sequential IDs "user_<n>", 64-bit FNV-1a:
  n = 1,000,000   RMSE 89.463%  mean -89.463%  worst -89.962%

// hll-check.cjs — node hll-check.cjs   (Node 18+, no dependencies, ~15 s)
// HyperLogLog by hand: 64-bit hash, p = 14 (16,384 registers), linear counting
// below 2.5m. 30 seeded trials of 1,000,000 distinct UUID-shaped visitor IDs.
'use strict';

// ---- MurmurHash3 x86_32 over char codes (ASCII IDs) -------------------------
function murmur3(str, seed) {
  let h1 = seed | 0; const len = str.length, nb = len >> 2;
  for (let i = 0; i < nb; i++) {
    const j = i << 2;
    let k1 = str.charCodeAt(j) | (str.charCodeAt(j + 1) << 8) |
             (str.charCodeAt(j + 2) << 16) | (str.charCodeAt(j + 3) << 24);
    k1 = Math.imul(k1, 0xcc9e2d51); k1 = (k1 << 15) | (k1 >>> 17);
    k1 = Math.imul(k1, 0x1b873593); h1 ^= k1;
    h1 = (h1 << 13) | (h1 >>> 19); h1 = (Math.imul(h1, 5) + 0xe6546b64) | 0;
  }
  let k1 = 0; const t = nb << 2;
  switch (len & 3) {
    case 3: k1 ^= str.charCodeAt(t + 2) << 16;
    case 2: k1 ^= str.charCodeAt(t + 1) << 8;
    case 1: k1 ^= str.charCodeAt(t);
      k1 = Math.imul(k1, 0xcc9e2d51); k1 = (k1 << 15) | (k1 >>> 17);
      k1 = Math.imul(k1, 0x1b873593); h1 ^= k1;
  }
  h1 ^= len; h1 ^= h1 >>> 16; h1 = Math.imul(h1, 0x85ebca6b);
  h1 ^= h1 >>> 13; h1 = Math.imul(h1, 0xc2b2ae35); h1 ^= h1 >>> 16;
  return h1 >>> 0;
}
// 64-bit hash as two 32-bit halves: high half, then low half seeded by it.
let HI = 0, LO = 0;
function hash64(str) { HI = murmur3(str, 0x9747b28c); LO = murmur3(str, HI ^ 0x5bd1e995); }

// ---- HyperLogLog -------------------------------------------------------------
class HLL {
  constructor(p) { this.p = p; this.m = 1 << p; this.reg = new Uint8Array(this.m); }
  addHash(hi, lo) {            // index = top p bits; rho = leading zeros of the rest + 1
    const p = this.p, idx = hi >>> (32 - p), w = (hi << p) >>> 0;
    const rho = w !== 0 ? Math.clz32(w) + 1 : 32 - p + Math.clz32(lo) + 1;
    if (rho > this.reg[idx]) this.reg[idx] = rho;
  }
  add(str) { hash64(str); this.addHash(HI, LO); }
  merge(o) { for (let i = 0; i < this.m; i++) if (o.reg[i] > this.reg[i]) this.reg[i] = o.reg[i]; }
  estimate(useLinearCounting = true) {
    const m = this.m, r = this.reg; let sum = 0, zeros = 0;
    for (let i = 0; i < m; i++) { sum += 1 / (2 ** r[i]); if (r[i] === 0) zeros++; }
    const alpha = 0.7213 / (1 + 1.079 / m), raw = alpha * m * m / sum;
    if (useLinearCounting && raw <= 2.5 * m && zeros > 0) return m * Math.log(m / zeros);
    return raw;
  }
}

// ---- deterministic, distinct, UUID-shaped visitor IDs ------------------------
function mulberry32(a) {
  return function () {
    a |= 0; a = (a + 0x6d2b79f5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0);
  };
}
const HEXC = [48,49,50,51,52,53,54,55,56,57,97,98,99,100,101,102];
const BUF = new Array(36);
// first 32 bits are a bijection of i (so IDs never repeat); the rest is random
function makeIds(seed) {
  const rnd = mulberry32(seed * 2654435761 + 1), salt = mulberry32(seed + 77)();
  return function idAt(i) {
    const w0 = (Math.imul(i, 0x9e3779b1) ^ salt) >>> 0, w1 = rnd(), w2 = rnd(), w3 = rnd();
    let p = 0;
    const put = (x) => { for (let s = 28; s >= 0; s -= 4) { if (p === 8 || p === 13 || p === 18 || p === 23) BUF[p++] = 45; BUF[p++] = HEXC[(x >>> s) & 15]; } };
    put(w0); put(w1); put(w2); put(w3);
    BUF[14] = 52;                                   // version nibble '4'
    BUF[19] = HEXC[8 + ((w2 >>> 28) & 3)];          // variant nibble 8..b
    return String.fromCharCode.apply(null, BUF);
  };
}

module.exports = { murmur3, hash64, HLL, makeIds, mulberry32, get HI() { return HI; }, get LO() { return LO; } };

// 64-bit FNV-1a, exact, in two 32-bit halves (prime = 2^40 + 435)
function fnv64(s) {
  let hi = 0xcbf29ce4, lo = 0x84222325;
  for (let i = 0; i < s.length; i++) {
    lo = (lo ^ s.charCodeAt(i)) >>> 0;
    const a = lo * 435, nhi = hi * 435 + Math.floor(a / 4294967296) + ((lo << 8) >>> 0);
    lo = a >>> 0; hi = nhi % 4294967296;
  }
  HI = hi >>> 0; LO = lo >>> 0;
}

if (require.main === module) {
  const P = 14, N = 1_000_000, SWITCH = 40_960, TRIALS = 30;
  const m = 1 << P, pct = (x) => (100 * x).toFixed(3) + '%';
  const summary = (errs) => {
    const rmse = Math.sqrt(errs.reduce((s, e) => s + e * e, 0) / errs.length);
    const mean = errs.reduce((s, e) => s + e, 0) / errs.length;
    const worst = errs.reduce((w, e) => (Math.abs(e) > Math.abs(w) ? e : w), 0);
    return `RMSE ${pct(rmse)}  mean ${pct(mean)}  worst ${pct(worst)}`;
  };
  console.log(`node ${process.version}  p=${P}  m=${m} registers (${m} bytes)  trials=${TRIALS}`);
  console.log(`quoted standard error 1.04/sqrt(m) = ${pct(1.04 / Math.sqrt(m))}\n`);

  const atN = [], atSwitch = [];
  for (let t = 1; t <= TRIALS; t++) {
    const h = new HLL(P), idAt = makeIds(t);
    for (let i = 0; i < N; i++) {
      h.add(idAt(i));
      if (i + 1 === SWITCH) atSwitch.push((h.estimate() - SWITCH) / SWITCH);
    }
    atN.push((h.estimate() - N) / N);
  }
  console.log(`UUID visitor IDs, MurmurHash3 x2 (64-bit):`);
  console.log(`  n = 1,000,000   ${summary(atN)}`);
  console.log(`  n =    40,960   ${summary(atSwitch)}   <- just past the 2.5m switch to the raw estimator\n`);

  const seqFnv = [];
  for (let t = 1; t <= TRIALS; t++) {
    const h = new HLL(P), base = 1000000 + (mulberry32(t + 5)() % 50000000);
    for (let i = 0; i < N; i++) { fnv64('user_' + (base + i)); h.addHash(HI, LO); }
    seqFnv.push((h.estimate() - N) / N);
  }
  console.log(`sequential IDs "user_<n>", 64-bit FNV-1a:`);
  console.log(`  n = 1,000,000   ${summary(seqFnv)}`);
}