HyperLogLog
HyperLogLog approximates cardinality (distinct counting) from leading zeros of hash values, estimating huge distinct counts in a small fixed memory.
Purpose
To approximately count billions of distinct elements in fixed memory (~KB), used for unique-visitor statistics.
Mechanism
Hash each element, bucket by the first k bits, and record in each bucket the maximum number of leading zeros among the remaining bits. The cardinality estimate ≈α*m^2*∑2^M[i]. Relative error is about 1.04/√m. Redis PFCOUNT uses this.
Use cases
- Unique-visitor statistics
- Cardinality estimation
- Stream distinct counting