5
$\begingroup$

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?
Improve this question
$\endgroup$
1
  • 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$
    – Sasho Nikolov
    Apr 1, 2017 at 0:26

0

Reset to default

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.