Hong Life CalculatorsUnderstanding the HyperLogLog error and memory calculator — concept and principle
HyperLogLog (HLL) estimates how many distinct items a data stream contains, such as unique visitors or unique search queries, using a tiny fixed amount of memory. This calculator shows the trade-off at the heart of HLL: the precision p sets the number of registers, which fixes both the memory used and the typical relative error of the estimate.
How it is calculated
- Registers: m = 2ᵖ.
- Standard error: σ ≈ 1.04 ÷ √m, shown as a percentage.
- Memory: m × bits per register ÷ 8 ÷ 1,024 KiB.
Six bits per register is the usual choice because a register stores a count of leading zeros, which never exceeds 63 for a 64-bit hash.
The principle
Hash every item to a random-looking bit string. Among n random strings, the longest run of leading zeros is about log₂ n, because a run of r zeros has probability 2⁻ʳ. One such maximum is very noisy, so HLL uses the first p bits of the hash to pick one of m registers and keeps the maximum run separately in each. It then combines the registers with a harmonic mean and a correction constant. Averaging m independent estimates shrinks the error in proportion to 1 ÷ √m, and the analysis by Flajolet and colleagues gives the constant 1.04. Duplicates hash to the same value, so they never change the result.
Worked example
- Inputs: p = 14, 6 bits per register.
- Registers: 2¹⁴ = 16,384; √16,384 = 128.
- Standard error: 1.04 ÷ 128 = 0.008125, shown as 0.81%.
- Memory: 16,384 × 6 ÷ 8 ÷ 1,024 = 12 KiB.
These are the settings Redis uses for its PFCOUNT command, which its documentation describes as 12 KB with a standard error of 0.81%.
| Precision p (registers = 2^p) | Standard error |
|---|---|
| 3.5 | 30.92% |
| 7 | 9.19% |
| 10.5 | 2.73% |
| 14 | 0.81% |
| 17.5 | 0.24% |
| 21 | 0.07% |
| 28 | 0.01% |
How to read the result
The standard error is relative: for 10 million true distinct items, 0.81% is about ±81,000. Roughly 68% of estimates fall within one standard error and about 95% within two. Each increase of p by one doubles memory and divides the error by √2 (about 0.71), so going from 12 KiB to 48 KiB only halves the error.
Common mistakes
- Expecting exact counts; use an exact set when every item matters.
- Reading σ as a maximum error; larger deviations happen occasionally.
- Merging sketches built with different precisions or hash functions, which is not valid.
Frequently asked questions
How many items can HLL count?
With a 64-bit hash, far more than any real data set, while memory stays fixed at the size shown.
Can I combine two HLL sketches?
Yes, if they use the same p and hash: take the maximum of each register to get the sketch of the union.
Why not just use a hash set?
A set needs memory proportional to the number of distinct items, which can be gigabytes; HLL needs kilobytes.
Sources: P. Flajolet, É. Fusy, O. Gandouet, F. Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", AofA 2007 · S. Heule, M. Nunkesser, A. Hall, "HyperLogLog in practice", EDBT 2013 · Redis documentation, HyperLogLog (PFADD, PFCOUNT)