The original HyperLogLog paper claims that this probabilistic counting algorithm is near-optimal. The relevant section of the paper reads:Clearly, maintaining $\epsilon$-approximate counts till a range of $N$ necessitates $\Omega(\log \log N)$ bits. Indeed,  the cardinalities should be located in an exponential scale,  $1$, $(1+\epsilon)$, $(1+\epsilon)^2$, , $(1+\epsilon)^L=N$, which comprises $\log_{(1+\epsilon)} N$ intervals, necessitating at least $\log_2 \log_{(1+\epsilon)} N$ bits of information to  be represented.It also says the optimality result comes from the combination of the previous fact and a bound by Chassaing & Gerin for a wide class of algorithms based on order statistics.How do the authors go from approximating the number of unique elements in a set to maintaining $\epsilon$-approximate counts till a range of $N$?What is the link between the two results and what exactly is meant by combining the two? I could only find an asymptotic bound in the paper they mention, but the HyperLogLog paper authors say that they are within 4% of the optimal bound. What have I missed?If the bound by Chassaing & Gerin is only about a algorithms that are based on order statistics, what proves that there isn't an algorithm based on something else that performs better?
Why is HyperLogLog (near-)optimal?
ds.algorithms;approximation algorithms;data streams;probabilistic computation