Introduction

How many distinct people visited a website yesterday? It sounds trivial: keep a list of the IDs you have seen, and ignore repeats. With a billion visitors that list weighs gigabytes — and you need one for every page, every hour, every region.

The obvious exact method costs memory proportional to the number of distinct items. When the stream is bigger than your machine, "just remember everything" stops being an option.

HyperLogLog, published by Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier in 2007, answers the question with a stunning trade: it gives you the count to within a few percent using only kilobytes, no matter how astronomically large the true number is — and it never stores a single item.

Stream the Sketch

Below is a tiny HyperLogLog sketch with just a few buckets. Press Add items to stream values through it — some new, some repeats. The sketch never stores what it sees; it only remembers, per bucket, the longest run of leading zeros in the hashes it has met.

<p class="hint">A tiny <b>HyperLogLog</b> sketch with 16 buckets. Each click streams a batch of items (some new, many repeats) through it. The sketch stores only the longest run of leading zeros it has seen per bucket — never the items themselves. Watch the estimate chase the true distinct count while memory stays flat.</p>
<div class="stats">
  <div class="stat"><span class="lbl">True distinct</span><span id="truth" class="val">0</span></div>
  <div class="stat"><span class="lbl">HLL estimate</span><span id="est" class="val est">0</span></div>
  <div class="stat"><span class="lbl">Error</span><span id="err" class="val">0%</span></div>
  <div class="stat"><span class="lbl">Memory</span><span id="mem" class="val">80 bits</span></div>
</div>
<div id="buckets" class="buckets"></div>
<div class="btns">
  <button id="add" type="button">Add 2,000 items</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.stats { display: grid; grid-template-columns: repeat(4, 1fr); gap: .5rem; margin: .4rem 0 .8rem; }
.stat { background: #f1f4f8; border: 1px solid #dde4ec; border-radius: 8px; padding: .5rem .6rem; text-align: center; }
.lbl { display: block; font-size: .7rem; text-transform: uppercase; letter-spacing: .04em; color: #5a7088; }
.val { display: block; font: 700 1.15rem ui-monospace, monospace; color: #1d3557; margin-top: .15rem; }
.val.est { color: #0a7d33; }
.buckets { display: grid; grid-template-columns: repeat(16, 1fr); gap: 3px; margin: .2rem 0 .9rem; align-items: end; height: 90px; }
.bucket { background: #c9ccd1; border-radius: 3px 3px 0 0; display: flex; align-items: flex-start;
          justify-content: center; font: 700 11px ui-monospace, monospace; color: #1d3557;
          min-height: 6px; transition: height .25s; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// HyperLogLog (Flajolet, Fusy, Gandouet, Meunier, 2007).
// Hash each item to 32 bits. Use the first p bits to pick one of m = 2^p buckets;
// each bucket stores rho = 1 + (number of leading zeros) of the remaining bits.
// Estimate = alpha_m * m^2 / sum(2^-register), corrected for small ranges.
const P = 4, M = 1 << P;            // 16 buckets
const registers = new Int8Array(M); // O(log log n) bits each — here a small int
const seen = new Set();             // ground truth ONLY (not part of the sketch)
let total = 0, counter = 0;

// 32-bit string hash: FNV-1a, then a murmur3 avalanche finalizer so the bits
// are well-mixed (uniform leading-zero distribution is what HLL relies on).
function hash(str){
  let h = 0x811c9dc5;
  for(let i=0;i<str.length;i++){ h ^= str.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
  return h >>> 0;
}
// Leading zeros in the low (32 - P) bits, then +1, capped.
function rho(w, bits){
  let r = 1;
  for(let i = bits - 1; i >= 0; i--){ if((w >> i) & 1) break; r++; }
  return Math.min(r, bits + 1);
}
function alpha(m){
  if(m === 16) return 0.673;
  if(m === 32) return 0.697;
  if(m === 64) return 0.709;
  return 0.7213 / (1 + 1.079 / m);
}
function offer(item){
  const x = hash(item);
  const idx = x >>> (32 - P);          // first P bits = bucket
  const w = x & ((1 << (32 - P)) - 1); // remaining bits
  const r = rho(w, 32 - P);
  if(r > registers[idx]) registers[idx] = r;
}
function estimate(){
  let sum = 0, zeros = 0;
  for(let i=0;i<M;i++){ sum += Math.pow(2, -registers[i]); if(registers[i] === 0) zeros++; }
  let E = alpha(M) * M * M / sum;
  if(E <= 2.5 * M && zeros > 0) E = M * Math.log(M / zeros); // small-range correction
  return Math.round(E);
}
function render(){
  const truth = seen.size, est = estimate();
  document.getElementById('truth').textContent = truth.toLocaleString();
  document.getElementById('est').textContent = est.toLocaleString();
  const e = truth ? Math.round(Math.abs(est - truth) / truth * 1000) / 10 : 0;
  document.getElementById('err').textContent = e + '%';
  document.getElementById('mem').textContent = (M * 5) + ' bits';
  const box = document.getElementById('buckets'); box.innerHTML = '';
  const max = Math.max(1, ...registers);
  for(let i=0;i<M;i++){
    const d = document.createElement('div'); d.className = 'bucket';
    d.style.height = (6 + registers[i] / max * 80) + 'px';
    d.textContent = registers[i] || '';
    box.appendChild(d);
  }
}
function addBatch(){
  // Stream a batch with a growing universe of distinct values plus heavy repeats.
  for(let i=0;i<2000;i++){
    // ~30% chance to mint a fresh distinct id; otherwise repeat an old one.
    if(Math.random() < 0.30) counter++;
    const id = 'user-' + (1 + Math.floor(Math.random() * Math.max(1, counter)));
    seen.add(id); offer(id); total++;
  }
  render();
}
document.getElementById('add').addEventListener('click', addBatch);
document.getElementById('reset').addEventListener('click', ()=>{
  registers.fill(0); seen.clear(); total = 0; counter = 0; render();
});
render();
Result
Console

Watch the estimate climb toward the true distinct count while memory stays flat. The intuition is a coin-flipping game: if the most extreme streak you have ever seen is k heads in a row, you have probably flipped about 2ᵏ times. A long run of leading zeros in a random hash is exactly that streak — so the rarest hash you have seen tells you roughly how many distinct items produced it.

The Real Complexity

Why does so little memory suffice? It comes down to what you actually need to know.

  • Exact counting is expensive. To never make a mistake you must remember which items you have already seen — provably linear memory in the number of distinct elements. There is no way around it if zero error is required.
  • The leading-zeros trick. Hash each item to a random bit string. The maximum number of leading zeros seen, ρ, behaves like the longest streak in a coin game: about 2^ρ distinct items are needed to produce a streak of length ρ. A single bucket gives a noisy estimate.
  • Averaging with buckets. HyperLogLog splits the hash to route items into m buckets and combines them with a harmonic mean, taming the variance. Each bucket only stores a small integer — O(log⁡log⁡n)O(\log \log n) bits — hence the name.
  • The accuracy law. The relative error is about 1.04/√m. With m = 2048 buckets that is roughly 2.3% error in around 1.5 KB, for any cardinality up to billions.

So HyperLogLog does not beat the lower bound for exact counting — it sidesteps it by accepting a small, controllable error. This is the streaming-algorithm bargain, the same spirit as Bloom filters: trade a little certainty for an enormous memory win.

Where It Matters

"How many distinct X?" is one of the most asked questions in data systems, and HyperLogLog answers it cheaply almost everywhere:

  • Web analytics: unique visitors per page, per day, per region — millions of counters that would never fit if each stored a full ID set.
  • Databases and warehouses: Redis (PFCOUNT), Presto, Apache Druid, Google BigQuery and Amazon Redshift all ship approximate COUNT(DISTINCT) built on HyperLogLog.
  • Networking and security: counting distinct source IPs or ports in a traffic stream to spot scans and floods.
  • Mergeable counts: two sketches can be combined by taking the per-bucket maximum, so you can count distinct users across a whole cluster by merging tiny summaries.

Understand HyperLogLog and you understand the broader family of probabilistic sketches — the same trade behind Bloom filters and other tools that summarize unbounded data in bounded space.

Conclusion

HyperLogLog turns a humble observation — that a long run of leading zeros is rare, and rarity measures how many tries you took — into a tool that counts the uncountable. It never stores an item, and its memory barely grows as the count explodes from thousands to billions.

The lesson reaches past one algorithm. When perfect answers cost too much, the smartest move is often to ask for an almost perfect one. Accept a few percent of error and the impossible becomes a kilobyte. The next time a dashboard tells you "1.2 million unique visitors," remember: nobody counted them. A few hundred tiny counters watched the coin flips and made a very good guess.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hyperloglog/Content licensed under CC BY-NC 4.0.