I was teaching the HyperLogLog estimator in class earlier this week and a student asked where the “hyper” bit came from. I know that HyperLogLog is a refinement/improvement to the LogLog estimator, so in one sense “HyperLogLog” makes sense as a way of saying “a better LogLog.” What I wasn’t sure about was whether there were any specific parts of the analysis or design that specifically would merit the term (hypergeometric functions? hypergraphs? hyperbolas?).

Beyond just meaning “better than LogLog,” is there any specific mathematical reason for calling it “HyperLogLog?”

  • 7
    $\begingroup$ If you read the original paper by Flajolet, Fusy, Gandouet, and Meunier, there is this note (Footnote 1): The paper [10] also introduces a variant called SUPERLOGLOG, which attempts to achieve variance reduction by censoring extreme data. It has however the disadvantage of not being readily amenable to analysis, as regards bias and standard error. One can assume HyperLogLog is what comes naturally after SuperLogLog. $\endgroup$ – Clement C. May 2 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.