Recording intelligenceAI-generated brief · check the source for context

HyperLogLog — count millions of unique things in a few KB

11:10 recording · EN · 1 speaker

Watch the original

Executive Summary AI
  • The recording opens on a short-video feed watched by millions and the question that is hard to answer: how many different people watched one clip, not how many views, because counting exactly means remembering every viewer, which grows to billions of entries.
  • HyperLogLog throws that list away and returns an estimate instead of an exact number, usually within about 1% (about 8.2 million rather than exactly 82 lakh 31,004), and it can never say whether one specific person watched.
  • The idea is a lottery: every viewer gets a scratch card decided by their ID, only the rarest win seen is kept, and because the same person always gets the same card, a repeat viewer adds nothing.
  • To stop one freak card from wrecking the estimate, viewers are split by ID across about 16,000 boxes, each running its own lottery, and a typical box's little crowd is multiplied by 16,000 — a hundred per box gives about 1.6 million.
  • Two sketches merge box by box by keeping the bigger rarest win, which never double counts, so servers, days or regions can be added freely — Redis, Reddit and data warehouses rely on this — but you cannot subtract a day back out or find an overlap.

Brief overview

HyperLogLog counts millions of different viewers in about 12 kilobytes by keeping lottery cards, not people.

  1. Trade exactness for memory that never growsWhether a million people watch or a billion, it is the same 16,000 boxes and about 12 kilobytes, at roughly 1% error.
  2. The same person always gets the same cardBecause the card comes from the viewer's ID, watching 100 times changes nothing, which is why the count is of different people and not views.
  3. Merging adds crowds, it never subtracts themKeep the bigger rarest win box by box to combine servers or days, but you cannot remove a day later or find the overlap between two sets.

Questions this recording answers

10 questions, each answered where it is said
What problem does HyperLogLog solve?

It counts how many different people did something, such as how many unique viewers watched a clip today, rather than total views. Counting exactly means remembering every person, which grows to millions and billions of entries. HyperLogLog throws that whole list away and still gives the number, usually within about 1%, using almost no memory.

How accurate is HyperLogLog and what does it give up?

It gives an estimate, not an exact number: instead of exactly 82 lakh 31,004 people it says about 8.2 million, usually off by about 1%, sometimes a bit more. You give up being exactly right, and in return memory barely grows. It also cannot tell you whether one specific person watched.

How can the rarest lottery win estimate the size of a crowd?

If the odds of winning are 1 in 10 lakh and someone wins, about 10 lakh people probably played. A 1 in 100 win means about 100 players, a 1 in a crore win about a crore. Each viewer gets a scratch card, and keeping only the rarest win seen tells you roughly how many watched.

Why does a repeat viewer not increase the count?

A person's scratch card is decided by who they are, so the same person always gets the exact same card. If they watch 100 times, it is the same card 100 times over, producing no new win and changing nothing. That is why HyperLogLog measures different people rather than total views.

Why does HyperLogLog split viewers across 16,000 boxes?

A single rarest win is shaky: if the first of only five viewers gets a one in a million card, the estimate screams a million. Instead, each viewer goes into one of 16,000 boxes by ID, each box guesses its own crowd, and a typical box is multiplied up. A freak card only disturbs one box.

What is the scratch card in technical terms?

It is just a hash. The viewer's ID is hashed into a random looking row of zeros and ones, and the win is a run of leading zeros. Six zeros is a one in 64 result; 20 zeros is about one in a million. Each box stores only the longest run of leading zeros it has seen.

How much memory does HyperLogLog need?

The common setup uses about 16,000 boxes, fitting in about 12 kilobytes and landing within roughly 1%. More boxes give a steadier total but use a little more memory. Whether a million or a billion people watch, it is the same 16,000 boxes, so memory does not grow: about 12 kilobytes for a billion people.

How do you merge HyperLogLog counts from two servers?

Because a person always lands in the same box number on every server, you merge box by box, keeping the bigger rarest win of the two. That gives exactly the boxes one single server would have had, and never double counts. The same works for combining seven daily sets into weekly unique viewers.

What can't you do when merging HyperLogLog sketches?

Merging only ever adds crowds together. You can add up servers, days or regions freely, but you cannot subtract one day back out later, and you cannot find the overlap between two of them. Adding yes, subtracting no.

Where is HyperLogLog used in practice, and when should you avoid it?

Redis has it built in with a 12 kilobyte sketch, Reddit uses it to show post view counts, and most big data warehouses offer approximate count distinct built on it. Avoid it for billing, audits or anything you must defend, and if the set is small enough to count exactly, just do that.

Key Quote

“Not how many views, how many different people.”

— HyperLogLog — count millions of unique things in a few KB, at 0:12▶ watch at 0:12
Key Quote

“It only ever gives you the count, never a yes or no about one person.”

— HyperLogLog — count millions of unique things in a few KB, at 1:22▶ watch at 1:22
Key Quote

“Nobody counted the players, but the rarity of the win tells you how many were there.”

— HyperLogLog — count millions of unique things in a few KB, at 1:45▶ watch at 1:45
Key Quote

“A repeat viewer adds nothing at all.”

— HyperLogLog — count millions of unique things in a few KB, at 2:50▶ watch at 2:50
Key Quote

“So the total barely moves. One wild guess was shaky. 16000 small guesses side by side are steady.”

— HyperLogLog — count millions of unique things in a few KB, at 4:48▶ watch at 4:48
Key Quote

“About 12 kilobytes for a billion different people.”

— HyperLogLog — count millions of unique things in a few KB, at 6:47▶ watch at 6:47

Cite this

“HyperLogLog — count millions of unique things in a few KB.” https://www.youtube.com/watch?v=UNf6UR_5-_M. Transcript summary by WhipScribe, https://whipscribe.com/transcript-pages/hyperloglog-count-millions-of-unique-things-in-a-few-kb.html.

Report this page
What is wrong with this page?