Toolgeist › Developer

HyperLogLog Playground — Count Millions of Distinct Items in 4KB

A working HyperLogLog, not a diagram of one. A Murmur3 hash picks a register with its top bits and contributes a leading-zero count with the rest; each register keeps the maximum it has seen, and the harmonic-mean estimator turns that pattern of maxima into a distinct count. Linear counting handles small cardinalities and the standard large-range correction handles the top of the 32-bit space. Feed it 500,000 distinct users and it lands within roughly 1% using 4 KB — where an exact set would need several megabytes — and the error tracks the theoretical 1.04/√m standard error at every precision setting.

How to use HyperLogLog Playground — Count Millions of Distinct Items in 4KB

  1. Choose a stream size, from a thousand items up to half a million.
  2. Compare the estimate against the true distinct count and the theoretical error band.
  3. Drag precision b and watch accuracy trade against memory.
  4. Pick the duplicate-heavy stream to confirm repeats cost nothing.

Frequently asked questions

How is this different from a Bloom filter?
They answer different questions. A Bloom filter tells you whether a specific item has been seen and needs space proportional to the number of items. HyperLogLog tells you how many different items there were and needs the same few kilobytes whether the stream had a thousand rows or a billion. It cannot tell you which items it counted — that information is genuinely gone.
How accurate is it really?
The standard error is 1.04/√m, where m is the register count. With m = 4096 that is about 1.6%, and quadrupling m halves the error. This page shows the theoretical band next to the observed error so you can check the claim rather than take it on faith — and pulling precision down to b = 4 makes the estimate visibly useless, which is the honest other half of the trade.
Why do duplicates not inflate the count?
A register only ever moves up to a maximum it has not yet reached, so re-adding an item that has already been added changes nothing at all. Select the "10k users, seen 20 times each" stream: 200,000 events go in and the estimate stays near 10,000. This is what makes it usable on unbounded streams with no deduplication step.
Can I combine sketches from different servers?
Yes, and that is the real superpower. The union of two HyperLogLogs is the register-wise maximum, so per-server or per-hour sketches merge after the fact into distinct counts over any time range or machine set — without re-reading raw data and without double-counting users appearing in both. That mergeability is why Redis, Presto, BigQuery and Druid all ship it.
Why are the small-cardinality numbers exact?
Below about 2.5m the estimator switches to linear counting, which uses the number of still-empty registers and is far more accurate in that range. With only a handful of items nearly every register is empty, so the count comes out essentially exact. The switch is visible in the estimator label on the page.
Where is it used in production?
Counting unique visitors, distinct IPs, unique search terms, or cardinality estimation inside query planners — anywhere the exact answer is not worth the memory. Redis exposes it directly as PFADD and PFCOUNT, using about 12 KB per key for roughly 0.81% error.

Related Developer tools

Also searched for: hyperloglog explained · count distinct approximate algorithm · cardinality estimation demo · redis pfcount how it works · probabilistic data structure distinct count

Browse all 738 free tools on Toolgeist →