Bigger Sketch, Same Miss
HyperLogLog counts distinct items in a fixed, small amount of memory: m registers, each remembering the longest run of leading zeros among the hashes that landed in it. Its error is usually quoted as one number, 1.04/√m, which is 0.81% for the 16,384 registers Redis uses. That number is the limit for large counts. I measured the error across the whole range, from one item to 64 times the register count, for the original estimator and the four fixes that came after it.
The short version: the original 2007 estimator has a spike just above 2.5m, where its error jumps to about 2.5% no matter how many registers you give it. For 16,384 registers that's 3.1 times the advertised error; for 65,536 it's 6.2 times. The later fixes remove it, and the best one, Otmar Ertl's 2017 estimator, needs no tables at all. Up to about 5m, the good ones actually beat the advertised number.
The estimators
- Original (Flajolet et al., 2007): the harmonic-mean "raw" estimate, but if that comes out at or under 2.5m and some registers are still empty, use linear counting instead (m ln(m/empty registers)). This is the version most write-ups teach.
- Redis 3.2: the original plus a fitted polynomial that subtracts the raw estimate's bias between 2.5m and 72,000, for 16,384 registers only.
- HLL++ (Heule, Nunkesser and Hall, 2013): subtract an empirical bias, looked up from a table of simulated runs, and switch to linear counting below a per-size threshold. I built my own table from 2,000 training runs per size, separate from the test runs.
- LogLog-Beta (Qin et al., 2016; Redis 4): one formula with a fitted 8-term correction for empty registers. I used Redis's coefficients at 16,384 registers and my own least-squares fit at every size.
- Ertl's improved estimator (2017; Redis 5 and later): corrects for empty and saturated registers analytically. No tables, no switch.
Each test was 10,000 independent runs per register count (1,024, 4,096, 16,384 and 65,536), each adding up to 64m distinct items and recording the estimates at several hundred checkpoints along the way. Hashes were ideal 64-bit random values. Two checks before trusting it: linear counting's spread matched Whang's closed form within 3%, and 200 runs that hashed actual strings with SHA-1 (4,096 registers) were indistinguishable from 200 ideal runs: for Ertl's estimator the ratio of their spreads stayed between 0.87 and 1.13 at every count from 64 up, and their means differed by more than two standard errors at 2.5% of checkpoints, about what chance gives.
The spike, and why more registers don't help
The raw estimate is badly biased upward at small counts, which is why the original switches to linear counting. The trouble is where it switches back. Measured as a fraction of the true count, the raw estimate's bias is:
| true count | m | 2m | 2.5m | 3m | 4m | 5m |
|---|---|---|---|---|---|---|
| raw estimate bias | +31.6% | +5.5% | +2.5% | +1.0% | +0.2% | 0.0% |
Same to within 0.1 points at all four sizes.
So the original hands over to the raw estimate while it's still about 2.5% high. Because the switch is on the estimate rather than the true count, it happens at a true count of about 2.43m, and from there almost every run reports the biased raw number until the bias fades out past 3m. The bias is a fixed fraction of the count, the same for every sketch size, while the advertised error shrinks with √m. More registers make the rest of the curve better and leave the spike where it was:
| registers | advertised | original, peak | Ertl, peak |
|---|---|---|---|
| 1,024 | 3.25% | 4.27% (1.3×) | 2.93% |
| 4,096 | 1.62% | 2.87% (1.8×) | 1.46% |
| 16,384 | 0.81% | 2.55% (3.1×) | 0.73% |
| 65,536 | 0.41% | 2.50% (6.2×) | 0.37% |
Peak RMS error for true counts between m and 5m. For the original the peak is at about 2.43m to 2.48m, at the two larger sizes almost all of it bias; for Ertl it's near 5m, on the way up to the advertised value.
In counts: with 16,384 registers, every true count from about 39,800 to 48,300 has more than 1.5 times the advertised error, and at 40,700 the 99th-percentile miss is 3.9%. It's bias, not noise: at that count the sketch reads high in nearly every run.
The fixes
At 16,384 registers, Redis's polynomial patch took the worst error from 3.1× down to 1.12× the advertised value, with a small leftover bump just before the switch. LogLog-Beta with Redis's coefficients, my refit LogLog-Beta, HLL++ with my bias table, and Ertl's estimator all peaked at 1.00×, and only at 45m, where every estimator converges to the advertised value anyway. The other sizes look the same. At 16,384 registers their largest bias anywhere from m/64 to 64m: Ertl 0.016%, LogLog-Beta 0.03%, HLL++ 0.09%.
Two details I didn't expect:
- HLL++'s switch threshold barely matters. I set mine where linear counting's error crosses the bias-corrected estimate's, which came out at 1.2m for 16,384 registers; the paper's value is 11,500, or 0.7m. The two error curves are nearly level with each other there, and using the paper's threshold instead changed the worst error below 5m from 0.905× to 0.926× the advertised value.
- My least-squares fit of LogLog-Beta's eight coefficients came out completely different from Redis's (one of them is −1.18 where Redis has +0.17), yet the two gave the same errors. The polynomial is so badly conditioned that many coefficient sets trace the same curve, so its coefficients shouldn't be read as meaning anything.
And the good news hidden in the left chart: below m, every estimator except the uncorrected raw one runs at 0.66 to 0.83 times the advertised error. Small counts are the easy part.
What I'd use
Ertl's estimator. It's about twenty lines that run on a histogram of the register values, has no tables or thresholds to get right for each sketch size, and was the most accurate of everything I tested. If you're using a library, check which estimator it implements: anything that switches at 2.5m with no bias correction will be about 2.5% high for counts a little over 2.4 times its register count, however big you make it.
Limits: ideal hashing with 64-bit hashes, so no 32-bit large-range correction, and registers wide enough never to overflow; the real-hash check covered one size. I didn't test Ertl's maximum-likelihood estimator or HLL++'s sparse mode, which stores small sets exactly and does better than any of these at tiny counts. My HLL++ bias table is built the paper's way but isn't Google's.
Try it. The sketch sizer turns these curves into a table: give it the range of counts you expect and a target error, and it shows the worst error each register count really gets over that range, for the original estimator or a bias-corrected one.