Expert · Module 24 · Lesson 3 of 4
HyperLogLog
HyperLogLog counts distinct items in fixed memory: every hash updates one tiny register by taking a maximum, and the pattern of register values estimates the cardinality within about 1.04/sqrt(m). It never stores an item and merges by taking per-register maximums.
By the end you can
- Follow how each item updates one register and why the update keeps a maximum
- Estimate a cardinality from the registers and quote the error for a register count
- Merge two HyperLogLogs into an estimate of the union and say what it costs
Builds on What a hash function does, Randomized algorithms.
01 · A question first
Feed Redis six words with PFADD and PFCOUNT answers 6, exactly. Feed it ten million user IDs and it returns a figure that misses by a few tenths of a percent — from a structure that stores none of the IDs and fills about 12 KB. How does counting work when you keep none of the things you counted?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Counting a set you refuse to store
- Registers that record luck
- Turning registers into a number
- What p buys, in bytes and in error
- Merging without moving IDs
- Where HyperLogLog does the work
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem