HyperLogLog (HLL) is a streaming algorithm that estimates how many distinct keys it has seen. A market-data team can use it to estimate how many distinct instruments sent quotes across several collectors in a session. Each collector keeps a compact summary called a sketch and can discard each instrument ID once it has updated the sketch. Memory for the register array stays fixed as new instruments appear. Flajolet et al., §1
What each register remembers
Hash each ID consistently, then split the hash into a prefix and suffix. The first bits select one of buckets. In the remaining bits, count the leading zeros and add one to get the rank. A suffix starting with a 1 has rank 1. An all-zero suffix of length has rank . Each bucket has a register, initially zero, that stores the largest rank seen in that bucket. Flajolet et al., §4, Figure 3
If hash bits are independent and equally likely to be 0 or 1, each extra leading zero halves the chance of seeing at least that many. A high rank is therefore evidence that the bucket has seen many distinct keys. One rare suffix can occur by chance, which is why HLL combines information across buckets. Flajolet et al., §§1–2.1
In the synthetic trace below, the first hash has prefix
0011 and suffix 00100000. The prefix selects bucket 3 and the two leading zeros give rank 3. The next hash also selects bucket 3, but rank 1 leaves the register at 3. The third puts rank 2 in bucket 10. Replaying the first ID reproduces its original bucket and rank.
The highlighted suffix bits are the ones used to compute the rank.
How the registers become an estimate
For register values , the raw estimate is
where corrects the scale. This is a scaled harmonic mean of the values , so an unusually large register has less influence than it would in an arithmetic mean. When many registers are still zero, the raw estimate tends to overcount. The original practical algorithm can use linear counting, , in its small-count range when registers are empty. It inverts an occupancy approximation. If distinct keys land uniformly and independently, roughly buckets are empty on average. HyperLogLog++ changes when it switches estimators and applies a bias correction to the raw estimate in part of the range. Flajolet et al., §§1 and 4, Heule et al., §5.2
For large cardinalities under the ideal hash model, the classical relative standard error is about . For 4,096 registers this is about 1.6%. That percentage describes the spread of estimates under the hash model. Individual errors can be larger. Small-count bias and collisions as cardinality approaches the size of the hash space call for separate treatment. Flajolet et al., Theorem 1 and §4
Merge sketches before estimating the union
If several collectors can see the same instrument, adding their distinct counts counts that instrument more than once. For compatible register arrays, take the larger of the two values in each corresponding register, then estimate from the merged sketch. The maximum of the per-collector ranks in each bucket is exactly the rank you would have kept in that bucket by processing all the feeds together.
Direct register-wise merging requires the same key definition and encoding, hash function and seed, precision, and bucket and rank conventions. Stored sketches follow their system’s merge rules. For example, BigQuery's HLL++ merge requires the same underlying input type and reduces mixed precisions to the lowest one. Google Cloud,
HLL_COUNT.MERGEThe SelfMadeQuant lesson on hash tables and universal hashing explains the random bucket model and how collisions arise. The full lesson requires membership.