Count Distinct
Every other machine here computes something exactly and then proves it. This one is wrong on purpose. You give up the exact answer, you get it back in kilobytes instead of gigabytes, and the trade is only worth making because the size of the error is known before a single item arrives.
One item, a register, an estimate, and how wrong it was
1 Hash one item, and read the bits
The algorithm never stores what you give it. It hashes the item and keeps one small fact about the hash. That is why the paper can claim, in its own abstract, cardinalities well beyond 109 with “a typical accuracy of 2% while using a memory of only 1.5 kilobytes”, and why nothing here can tell you which items it saw.
- its hash
- 2,290,972,270
register: 1000100010 rest: 0011010111011001101110
2 A register from the front, a run of zeros from the rest
The first 10 bits choose one of 1,024 registers. In whatever is left, the algorithm finds the position of the leftmost 1 and keeps it, but only if it beats what that register already holds. A long run of leading zeros is rare, so seeing one is evidence that a lot of different things have gone past.
- register
- 546
- the rest
- 22 bits
- rho
- 3
- the leftmost 1 is in position 3
3 The estimate, beside the exact count
Now a whole stream. These items are distinct by construction, so the page knows the true answer without counting anything, and every estimate below is shown against the number it is estimating. A demonstration that hides that is an advertisement.
- exact count
- 5,000
- estimate
- 4,940
- off by
- -1.20%
- expected
- ±3.25%
- correction used
- intermediate
- empty registers
- 5 of 1,024
- memory
- 1,024 bytes
- with the arithmetic mean
- 29,804 (+496.07%)
the first 128 of 1,024 registers
The last row above is the same estimator with one thing changed: the mean. Every register holds the longest run of zeros it has seen, and a run that long is rare, so the tallest bar above is a register that got lucky rather than one that saw more. An arithmetic mean lets that register answer for all of them. The harmonic mean is dominated by the small values instead, which is why the published estimate sits within a few per cent of the truth and that row does not.
The picture draws the first 128 registers. This reaches any of them, including the ones past the edge of it.
- its index, in bits
- 0000000000
- it holds
- 5
- which means
- a run of 5 zeros before the first 1, so this register alone would guess 2^5 = 32
- items landed here
- 6 items
That last row is this page's bookkeeping, not the algorithm's. HyperLogLog keeps one small number per register and could not tell you how many things went into it, which is the whole reason it fits in a kilobyte.
4 How wrong it is, over many runs
This is the stage the other explanations of this algorithm leave out, and it is the only part that is genuinely hard to believe. The paper does not claim the estimate is close. It claims a distribution: a standard error of about 1.04 over the square root of the number of registers, with runs landing inside one, two and three of those about 65%, 95% and 99% of the time. One run cannot show that. So this runs the whole sketch again and again on fresh streams and plots where every run landed.
- spread observed
- —
- spread predicted
- —
- mean error
- —
Run it to see whether what is left is spread or bias.
The seam, which is why there is a second paper
Press on the seam above and run it. The spread will not change much, but the mean error walks away from zero and stays there. That is not noise: it is bias, and it is the 2007 algorithm's known weak point.
Below about two and a half registers' worth of items the algorithm abandons its own estimator and uses linear counting instead, because the harmonic mean is bad when most registers are still empty. Just above that threshold it switches back, and the raw estimate there reads high. The authors of HyperLogLog++ measured exactly this in 2013 and wrote it plainly: most of the error of the raw estimate, for small sets, is bias rather than spread, and the algorithm overestimates. Their fix was an empirical bias table and a 64-bit register scheme, which is a different algorithm and is not what this page runs.
So the honest summary is narrower than the headline. The 1.04 over root m is real, and you can watch it hold in the comfortable range. Near the seam the error is not centred on the truth, and no amount of running it more times will centre it.
What this page is not telling you
The count of items per register is this page's, not the algorithm's
The register inspector says how many items landed in the register you are looking at. HyperLogLog does not know that and could not tell you: it keeps one small number per register, the longest run of zeros it has seen, and that is the entire reason a kilobyte is enough. This page counts the landings separately as it builds the stream, purely so the load spread is visible. Everything else in that readout is read out of the sketch itself.
The hash is not the paper's, because the paper does not have one
The algorithm is specified over “a suitable hash function”, and every guarantee it has assumes the hashed values look uniform. A weak hash is the one way to make this thing quietly wrong while every readout still looks reasonable. This page uses an FNV-1a mix followed by MurmurHash3's 32-bit finaliser, both of which are somebody else's work rather than something invented here, and the test measures the bit distribution instead of trusting it.
Thirty-two bits, so the large-range correction is reachable and the modern one is not
The 2007 paper hashes to 32 bits and needs a large-range correction, because at a cardinality approaching 232 the estimate runs into the top of the hash space itself. Everything in production now hashes to 64 bits, where that correction is unnecessary and is dropped. This page is 32-bit because it is implementing the 2007 paper, which means the third branch exists here and would not exist in anything you would actually deploy.
The items are distinct by construction, which is the easy case
Stage three builds a stream of items that are already all different, so the exact count is known without storing or comparing anything. Real streams repeat, and the whole point of the algorithm is that repeats cost nothing. Nothing here demonstrates that, because a stream with repeats would make the exact count a thing this page had to compute rather than a thing it knows.
The alpha constants are the paper's rounding, not the paper's definition
Alpha is defined by an integral, and the four values in the pseudocode are that integral rounded to three or four places. This page uses the rounded values, because it is implementing the published algorithm rather than improving it. Integrating the definition gives 0.673102 where the paper says 0.673, and the test does that integration to make sure the difference is a rounding and not a mistake.
Nothing here is a benchmark
The memory figure is one byte per register, which is what the register array actually costs on this page. A production implementation packs registers into five or six bits each, keeps a sparse representation while the sketch is small, and would report a smaller number. No timing is claimed anywhere, and the runs in stage four are deliberately small enough to finish in a browser.
Sources
- Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier, “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”, Analysis of Algorithms 2007 — the algorithm this page runs, taken from the pseudocode in the paper rather than from an implementation. The three range corrections, the alpha constants and the 1.04 over root m are all from here. Free.
- Stefan Heule, Marc Nunkesser and Alexander Hall, “HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm”, EDBT 2013 — the source for the seam. It is the paper that measured the bias in the original estimator and says so directly: most of the error of the raw estimate is bias rather than spread, and the algorithm overestimates for small sets. Its own algorithm is not implemented here. Free.