Skip to content
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm 3 min

Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier · AofA 2007

HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

Count a billion unique visitors in about a kilobyte. See how leading zeros in hashes, many tiny registers and a harmonic mean make it work.

Read the original paper

Algorithms · Black Belt · Pro · 3 min read

HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

How many different people visited your website today? It sounds easy. Keep a list of visitor IDs, and count the entries. But for a site with a billion visitors, that list takes gigabytes, and you may need that number for every page, every hour, every country. Exact counting does not scale.

HyperLogLog, described by Philippe Flajolet and colleagues in 2007, estimates the number of distinct items in a huge stream using a few kilobytes. The paper's headline: it can estimate cardinalities well beyond a billion with a typical accuracy of 2 percent using only 1.5 kilobytes of memory.

Hash every item. Track the longest run of leading zeros you have seen, since rare patterns mean many items. Use many small registers to smooth out luck, then combine them. Memory stays tiny, and the error shrinks as 1 over the square root of the number of registers.

The coin-flip insight

Imagine each item turned into a random string of bits by a good hash function. Half of all strings start with a 1. A quarter start with 01. One in eight starts with 001, and so on. A string with k leading zeros appears about 1 time in 2k.

Rare patterns signal volume. The chance that a random bit string starts with k zeros is 1 in 2^k, so seeing one suggests that roughly 2^k distinct strings have gone by.

So if you scan a stream and the best you ever see is 3 leading zeros, the stream was probably short, a few dozen items at most. If you see 20 leading zeros, you have probably seen about a million different items. You only have to remember one small number: the maximum.

Duplicates cause no trouble. The same item hashes to the same string, so seeing it again cannot increase the maximum. That is why this counts distinct items.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • Many registers: averaging out luck
  • Why it is so handy

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.