Show HN: An improved version of HyperLogLog

Re:Show HN: An improved version of HyperLogLog by jbapple on Tuesday June 27, 2017 @10:29AM (#14645682)

So if a register overflows (and is truncated) "twice" by the same element before the base register (B) is increased, then after B is increased, the overflowing register is not increased and so appears not to have overflowed. On the other hand, if that element shows up in the stream once before and once after B is increased, the overflowing register may overflow again.

This makes even the MLE procedure partially incorrect in the first case, since it is the maximum likelihood estimation of a set of hashes in which the register discussed above did not overflow.

Is that about right?

[ Parent | on HN ]

Re:Show HN: An improved version of HyperLogLog by oertl on Tuesday June 27, 2017 @10:55AM (#14645940)

I have not yet checked their ML approach. Regarding register updates you are right.

I have also seen that they did only 10000 simulation runs to determine the standard deviation to be 1.00/sqrt(m). I think more simulations would be necessary to get a confidence interval for the standard deviation that is small enough to allow differentiation from 1.04/sqrt(m).

[ Parent | on HN ]