HyperLogLog
HyperLogLog is a probabilistic data structure used for estimating the cardinality (the number of distinct elements) of a set. It is famous for being able to count billions of unique items using a tiny, fixed amount of memory.
1. The Problem: Counting Distinct Items
Counting unique items (e.g., "How many unique visitors did my website have today?") is easy with a small dataset: just use a Hash Set.
However, if you have billions of visitors, storing every unique IP address or User ID in a Set requires massive amounts of RAM. An exact count becomes expensive.
2. The Solution: Probabilistic Counting
HyperLogLog trades a small amount of accuracy for massive memory savings. It doesn't store the actual elements. Instead, it observes the randomness of hashed values to estimate the count.
The Intuition (Coin Flips)
Imagine you flip a coin until you get heads.
- If you tell me it took you 1 flip, I'm not impressed.
- If you tell me it took you 10 flips in a row to get heads (0000000001), I assume you probably flipped the coin many, many times to get that lucky sequence.
HyperLogLog hashes every element to a binary string. It looks at the longest run of leading zeros in those hashes. The longer the run of zeros, the more distinct elements you have likely seen.
3. Accuracy vs. Memory
- Memory: A standard HyperLogLog implementation takes about 1.5 KB of memory to count up to $10^9$ (1 billion) items.
- Accuracy: The typical error rate is around 0.81%.
4. Operations
- Add: Hash the item and update the internal registers (buckets).
- Count: Calculate the estimate based on the registers (using harmonic mean to reduce outliers).
- Merge: You can merge two HyperLogLogs (e.g., merge "Monday Uniques" and "Tuesday Uniques" to get "Total Uniques") without losing precision.
5. Use Cases
- Big Data Analytics: Counting unique users, distinct search queries, or unique video views.
- Databases: Redis has built-in commands (
PFADD,PFCOUNT) for HyperLogLog. - Networking: Detecting distinct flows or IP addresses passing through a router.
programming/bloom-filters programming/hash-tables programming/distributed-systems