hyperloglog-estimation-error.md

HyperLogLog estimation error

The state of an HyperLogLog sketch with precision parameter $p$ requires $0.75 \cdot m = 0.75 \cdot 2^p$bytes where$m$denotes the number of registers. The expected relative standard error is approximately given by$\frac{1.039}{\sqrt{m}}$,$\frac{1.037}{\sqrt{m}}$, and$\frac{0.833}{\sqrt{m}}$for the default, the maximum-likelihood (ML), and the martingale estimator, respectively. This is a good approximation for all$p\geq 6$and large distinct counts. However, the error is significantly smaller for distinct counts that are in the order of$m$or smaller. The bias is always much smaller than the root-mean-square error (rmse) and can therefore be neglected. The following charts show the empirically determined relative error as a function of the true distinct count for various precision parameters$p$ based on 100k simulation runs. Distinct counts up to 1M were simulated by generating random values as hash values. For distinct counts above 1M, a different technique is used by randomly generating only hash values at distinct counts that can actually change the state of the data structure.