HyperLogLog Cardinality Sketch (64-bit hash, merge, serialization)

A from-scratch HyperLogLog sketch in Node. It includes a 64-bit hash (two seeded MurmurHash3 halves), precision p from 4 to 16, max-rank registers, the harmonic-mean estimator with alpha_m, linear counting for small cardinalities, Ertl's improved estimator as an alternative, lossless merge (including across different precisions), and 6-bit packed serialization. Tests check the error against 3 x 1.04/sqrt(m) on 100k and 1M seeded distinct items.

The problem

"How many distinct users/IPs/search terms/devices?" An exact answer needs memory proportional to the number of distinct items (a hash set of 100M ids is gigabytes), and exact sets from different shards or days can't be combined without shipping all of them. HyperLogLog answers within about 1% using 12 KB, and sketches merge with a register-wise max. That means per-shard, per-minute or per-partition sketches can be rolled up to any window or grouping later.

Where it shows up: Redis PFADD/PFCOUNT/PFMERGE, BigQuery APPROX_COUNT_DISTINCT and HLL_COUNT.*, Trino/Presto approx_distinct, Elasticsearch/OpenSearch cardinality aggregations, Druid and Apache DataSketches, Snowflake/Redshift approximate distinct, and the postgresql-hll extension.

Design

item ─► 64-bit hash ─► [ top p bits: register index j ][ remaining 64-p bits ]
                                                          └─► rank = leading zeros + 1   (1 .. 64-p+1)
registers[j] = max(registers[j], rank)

The intuition: in a stream of uniformly random bit strings, seeing a run of r-1 leading zeros suggests about 2^r distinct values. One register would be hopelessly noisy, so HLL splits the stream into m = 2^p sub-streams by the top bits and combines them with a harmonic mean, which resists outliers:

E_raw = alpha_m * m^2 / sum_j 2^(-M[j])
alpha_16 = 0.673, alpha_32 = 0.697, alpha_64 = 0.709, alpha_m = 0.7213 / (1 + 1.079/m) for m >= 128
if E_raw <= 2.5m and V registers are still zero:  E = m * ln(m / V)     (linear counting)

With a 64-bit hash, the 32-bit large-range correction from the original paper isn't needed: hash collisions stay negligible far beyond any realistic cardinality (Heule et al. 2013).

Hash. hash64 runs MurmurHash3_x86_32 twice with independent seeds to produce hi and lo. The test suite checks the implementation against the reference vectors and checks that all 64 output bits are balanced. Rank extraction crosses from hi into lo when the low 32-p bits of hi are all zero, so ranks up to 64-p+1 really occur. There is a unit test for each boundary.

Invariants

Registers only grow. add is idempotent, so duplicates never change the sketch (tested).
merge is register-wise max: commutative, associative and idempotent. a ∪ b is bit-identical to a sketch built from the union stream (tested with overlapping sets).
Sketches only merge if they share a hash seed. Merging different precisions first folds the finer sketch down. withPrecision(q) is exact: the p-q index bits that get dropped become the first bits of the remainder (new rank = their leading zeros + 1, or (p-q) + old rank if they're all zero). The tests show the result equals a sketch built directly at q.
Serialization: magic "HLL1" | version | p | seed u32 | registers packed 6 bits each (p=14 → 12,298 bytes). Decoding rejects bad magic, bad length, invalid p and ranks above 64-p+1.

Accuracy and complexity

Relative standard error is 1.04 / sqrt(m). That's 26% at p=4, 3.25% at p=10, 0.81% at p=14 and 0.41% at p=16. The tests assert:

every p in 4..16 is within 3σ at n = 100k and n = 1M
RMS error over 30 independent seeds is within [0.5σ, 1.5σ] of 1.04/sqrt(m), and the mean bias is small

Operation	Time	Space
`add`	O(len(item)) hash + O(1) register update	—
`estimate` / `merge` / `withPrecision`	O(m)	m bytes in memory, 0.75·m bytes serialized

Transition-zone bias. Just after the linear-counting switch-over (about 2.5m < n < 5m), the classic estimator is biased upward. At p=8 the demo measures about +2.3% at n = 2.6m, against about +0.8% for Ertl. That's why the 3σ test skips the classic estimator for p=15 at n=100k (n ≈ 3m) and checks only estimate('ertl') there. A separate test averages 300 runs to show the bump exists and that Ertl's estimator reduces it.

Failure modes and trade-offs

Small p is noisy. p=4 gives ±26%. Most systems use p=12–14. Error depends only on m, not on n.
No deletes, no exact intersection. Intersection by inclusion-exclusion (|A|+|B|-|A∪B|) takes on the absolute error of the large sets, which is terrible when the overlap is small. Use MinHash or Theta sketches for set similarity.
Hash quality and hash agreement are correctness. A biased hash biases the estimate. Sketches built with a different hash or seed merge into garbage, which is why the seed is serialized and checked.
Adversarial input. Anyone who knows the hash can craft items with huge ranks and inflate the count. Use a secret seed when inputs are attacker-controlled.
Memory at low cardinality. A dense sketch costs 12 KB even for 3 items. Production systems start with a sparse encoding.

How production systems do it

Redis uses p = 14 (16,384 registers, 0.81% standard error), with 6-bit registers in a 12 KB dense encoding, a run-length sparse encoding for small sets that is promoted automatically, and MurmurHash64A. Since Redis 5 it estimates with Ertl's improved algorithm, the same one as estimate('ertl'). PFCOUNT caches the last estimate in the header.
Google HLL++ (BigQuery, and the ZetaSQL/HLL_COUNT functions) uses a 64-bit hash, empirical bias-correction tables for n < 5m, and a sparse representation at a higher precision (p' = 25) that gives near-exact small counts.
Apache DataSketches (Druid, Spark, Hive) ships HLL_4/6/8 register widths, plus Theta and CPC sketches for better accuracy per byte and for set operations.
Elasticsearch cardinality uses HLL++ and is close to exact below a precision_threshold. Trino approx_distinct (the Airlift HLL) defaults to a 2.3% standard error and switches between sparse and dense representations.

Extension exercises

Add a sparse representation (a sorted list of (index, rank) pairs at a higher precision, as in HLL++) that converts to dense once it would be larger than 0.75·m bytes. Measure error for n < 1000.
Replace hash64 with a true 64-bit hash (xxHash64 or MurmurHash64A using BigInt or 16-bit limb multiplication) and benchmark throughput against the two-halves approach.
Build a sliding-window unique counter: one sketch per minute in a ring buffer, merged on query. What does a 24-hour query cost?
Implement 4-bit registers with an offset (like DataSketches HLL_4) and compare memory and error.
Estimate |A ∩ B| by inclusion-exclusion across a range of overlap ratios and plot where it becomes useless. Then compare with a MinHash (k=256) estimate.