HyperLogLog

War and Peace has 436,069 words, 47,585 of them distinct. To count them exactly you have to remember every word met so far: the letters alone take about 785 KB. And what if the words are a website’s visitors for a year, and there are billions of them? HyperLogLog answers the question “how many distinct” differently: it remembers not a single word, but keeps a few hundred small numbers and estimates the answer from them. Press Play: the novel flows word by word through the registers, and above them two lines grow, the exact number of distinct words and the estimate.

With 64 registers, 48 bytes, the estimate wanders around the truth by ten per cent or so. Switch to 1024 registers, 768 bytes: the lines almost merge. Above the chart is the hash of the current word: the first bits (highlighted) choose a register, and after them it is counted how many zeros come before the first one. The register remembers the longest such run. That is all the information HyperLogLog keeps.

The idea

Imagine someone tossed a coin all day and told you only one thing: the longest run of heads in a row was twelve. How many times was the coin tossed? A run of 12 heads happens about once in 2¹² = 4096 tries, so there were on the order of several thousand tosses. A word’s hash is 32 fair coin tosses: the bits of a good hash look random and independent. One and the same word always gives the same bits, so repeats add nothing: only distinct words count.

Hash each element. The first p bits of the hash choose one of m = 2^p registers, and in the remaining bits find the position of the first one, the rank. A register keeps the largest rank among the elements that landed in it. If about n/m distinct elements landed in a register, its value is close to log₂(n/m). The estimate is α_m·m² divided by the sum of 2^−M_j over the registers: the harmonic mean of the values 2^M_j, multiplied by m and a correction factor.

Why many registers rather than one? A single longest run is too noisy a measure: if you were lucky and the run came out two positions longer, the estimate is four times off. By splitting the stream into m independent parts and averaging, we reduce the error √m times. Why the harmonic mean and not the ordinary one? The lucky registers give huge values of 2^M_j, and the harmonic mean is almost insensitive to such outliers; this is the difference between HyperLogLog and its predecessor LogLog, where the registers were averaged in the exponent.

How accurate

The proof by Flajolet and co-authors runs to dozens of pages and rests on delicate analysis, so here is a check instead. Below, all 47,585 distinct words of the novel are counted a hundred times, each time with a different hash seed, that is, with its own “coin tosses”. Each dot is the error of one run, and the band is ±1.04/√m.

About two thirds of the dots are inside the band, as there should be for one standard deviation. With 1024 registers the band is ±3.25%, with 16,384 ±0.81%: 16 times more memory gives a four times smaller error. The memory is tiny all the same: 6 bits are enough for a register, because a run of zeros in a 32-bit hash is at most 32 long. 16,384 registers are 12 KB, and they would take the same for a billion distinct elements.

When there are few distinct elements

The formula assumes that something has landed in every register. While there are fewer distinct elements than registers, many registers are empty, and the formula greatly overestimates: for a single element and 1024 registers it gives about 739. For this case there is a correction from another problem, about balls and bins. If n balls are thrown into m bins at random, about m·e^−n/m bins stay empty. So from the number of empty registers V one can estimate n ≈ m·ln(m/V). This technique is called linear counting, and HyperLogLog switches to it when the estimate is at most 2.5·m and there are still empty registers. Look at the start of the first scene: the estimate is accurate from the very first words precisely thanks to it.

Merging is a maximum

The sketch has a property for which HyperLogLog is used in distributed systems. If two streams are counted by two sketches with the same hash, the sketch of their union is the elementwise maximum of the registers: each element would land in the same register with the same rank. So servers can each count their own and then add the sketches together; days can be merged into weeks, weeks into a year, and the error does not pile up. In the listing below the two halves of the novel are counted separately: the sum of their estimates gives 62,545, each shared word counted twice, while the maximum over the registers gives 47,761 against the exact 47,585.

With intersection it does not work like that: it is estimated through inclusion and exclusion, |A ∩ B| = |A| + |B| − |A ∪ B|, and the errors of the three estimates add up. If the intersection is small compared with the sets, its estimate drowns in the noise.

Code

The same MurmurHash3 hash as in the scenes, on the whole text of the novel from the sandbox: estimates with 64, 1024 and 16,384 registers and the merging of two halves.

The errors of this run, +7%, +1.8% and +1.0%, fit into the typical 13%, 3.25% and 0.81%, although the last is slightly more than one standard deviation: it is a single estimate, not an average. The register is chosen by the high bits of the hash, and the rank is computed in the low bits: bit_length in Python and bits.Len32 in Go give the length of the number, and the first one stands right after the zeros that fall short of this length.

What it costs

Adding an element is one hash and one comparison, O(1). An estimate is a pass over the registers, O(m), and merging two sketches is O(m) too. Memory is m registers of 6 bits however many elements have gone by. An exact count needs memory proportional to the number of distinct elements: a hash set of 47,585 words is hundreds of kilobytes, and of a billion identifiers tens of gigabytes. Compare with a Bloom filter: it answers “has this element been seen” and spends bits on each element, while HyperLogLog answers only “how many distinct were there” and does not grow at all.

Where it works

Redis. The PFADD, PFCOUNT and PFMERGE commands keep a HyperLogLog with 16,384 registers: up to 12 KB per key and a standard error of 0.81%. The PF prefix, as the author of Redis, Salvatore Sanfilippo, wrote, is in honour of Philippe Flajolet. For small sets Redis keeps the sketch in compressed form and expands it as it grows.

Analytics. The APPROX_COUNT_DISTINCT function in Google BigQuery is built on HyperLogLog++, a variant described by Google engineers in 2013: a 64-bit hash, an empirical bias correction for medium numbers and a sparse representation for small ones. “Unique visitors per month” reports in web analytics systems are counted the same way: a sketch is kept for each day, and for any period they are combined by maximum.

Databases. A query planner needs to know how many distinct values a column has to choose the order of table joins. An exact count over a large table is expensive, while a sketch is updated on the fly.

History

The idea of estimating the number of distinct elements from the bits of hashes belongs to Philippe Flajolet and Nigel Martin: in 1985 they described probabilistic counting, which tracks which positions of the first one have already occurred. In 2003 Marianne Durand and Flajolet proposed LogLog with registers and an average in the exponent, and in 2007 Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier proposed HyperLogLog with the harmonic mean and an error of 1.04/√m. Flajolet died in 2011; three years later the HyperLogLog commands in Redis were given Flajolet’s initials.

Problems

In the first problem the estimate has to be computed from hashes, with the right bits and the small-range correction. In the second you are given the sketches of all the chapters of the novel and have to estimate quickly the number of distinct words in any range of chapters: merging is a maximum over the registers, and the maximum over a range is a sparse table.