HyperLogLog Register Harmonic Estimate
Estimate distinct values from bucketwise leading-zero maxima and a harmonic aggregate.
By Riano · Published · Updated · Report a correction
HyperLogLog Register Harmonic Estimate
Estimate distinct values from bucketwise leading-zero maxima and a harmonic aggregate.
Worked Example
Consider an empty HyperLogLog state with m = 16 registers and a stream of 1 element: 2048. First, calculate the raw estimate and then apply the small-range correction.
| Variable | Calculation | Result |
|---|---|---|
| Input hash | 2048 | 0000 1000 0000 0000 |
| Bucket | Top 4 bits | 0 (0000) |
| Lower 12 bits | Remaining bits | 1000 0000 0000 |
| Leading Zeros | in lower 12 bits | 0 |
| Rank | Leading Zeros + 1 | 1 |
| Registers | M[0] = 1, others 0 | 15 zeros, one 1 |
| Raw Estimate | (0.673 * 162) / (15 * 2-0 + 2-1) = 172.288 / 15.5 | 11.115354838709678 |
| Small Range Correction | 16 * ln(16 / 15) | 1.0326163382011386 |
Experiment
Using the module at https://riano.app/module/hyperloglog-register-harmonic-estimate, try the following configurations:
- Set Stream to "Empty" and Prefix to "16". Notice the raw estimate is 10.768, and corrected is 0.
- Set Stream to "Repeated" and Prefix to "16". The stream contains the exact same hash (2048) 16 times. Observe that only one register (M[0]) becomes 1, giving a corrected estimate of ~1.03.
- Set Stream to "Mixed" and Prefix to "16". This shows typical behavior when hash functions distribute items among various buckets.
- Set Stream to "Spread" and Prefix to "16". Notice that the exact distinct hashes count is perfectly predicted by the corrected estimate.
Limitations
This module uses a pedagogical predefined set of small integer hashes rather than an actual hash function. Real applications use a uniform hash function like MurmurHash3 to minimize collisions. Additionally, this module uses only 16 registers (m=16) for demonstration; real systems use much larger numbers of registers (e.g., m=4096 or more) for practical accuracy. When the raw estimate is less than or equal to 2.5 * m (40 in this case), and there are empty registers, Linear Counting is used for a corrected estimate. Otherwise, the raw estimate is used.
References
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm".https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive HyperLogLog Register Harmonic Estimate module.
Try HyperLogLog Register Harmonic Estimate on Riano →