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".

  1. 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$"?
  2. What is the link between the two results and what exactly is meant by combining the two?
  3. 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?
  4. 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?
  • 7
    $\begingroup$ The first observation is rather simple. The memory contents of the algorithm should allow you to tell whether the number of distinct elements is in $[1, 1+\varepsilon)$, or in $[1+\varepsilon, (1+\varepsilon)^2)$, ..., $[(1+\varepsilon)^{L-1}, (1+\varepsilon)^L)$. These are $L$ distinct intervals, so the memory of the algorithm should have at least $L$ distinct states, so it should consist of at least $\log_2 L$ bits. $\endgroup$ Apr 1, 2017 at 0:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.