A HyperLogLogA probabilistic cardinality estimator: hash each item, bucket it by its first bits, and in each bucket keep the longest run of leading zeros seen. The pattern of those maxima reveals roughly how many distinct items went by. answers "how many distinct things have I seen?" without keeping any of them. The trade is a little fuzz on the count — and a fixed, tiny memory that doesn't grow whether you tally a thousand items or a billion. The single knob is precision: more registers, less error, more bytes. Pick your end of the trade.
At 14 bits of precision — 16k registers — the estimate lands within about ±0.813% of the true count, using 12 KiB. That holds whether you count a thousand items or 1M; storing 1M exactly would take ~7.6 MiB.
Error falls as 1.04 / √m, so each extra bit of precision doubles the registers (and the memory) but only shrinks the error by √2 ≈ 0.71. Halving the error costs 4× the memory — diminishing returns, though the bytes stay small for a long time.
| Precision | Standard error |
|---|---|
| 8 bits256 regs192 B | ±6.5% |
| 10 bits1k regs768 B | ±3.25% |
| 12 bits4k regs3 KiB | ±1.63% |
| 14 bits16k regs12 KiBnow | ±0.813% |
| 16 bits64k regs48 KiB | ±0.406% |
| 18 bits256k regs192 KiB | ±0.203% |
The memory column is the whole story: p = 14 is Redis's default — 16k registers, ~12 KiB, within ±0.8% — and it counts billions just as well as thousands. A sparse encoding shrinks it further while the count is small. Spend precision only where the extra accuracy earns its bytes.
Have a target error in mind? Size it from the error →