hyperloglog – Tarik Billa

LogLog and HyperLogLog algorithms for counting of large cardinalities

April 2, 2023 by Tarik

Here it is the updated version of the algorithm based on the newer paper: var pow_2_32 = 0xFFFFFFFF + 1; function HyperLogLog(std_error) { function log2(x) { return Math.log(x) / Math.LN2; } function rank(hash, max) { var r = 1; while ((hash & 1) == 0 && r <= max) { ++r; hash >>>= 1; } … Read more

How does the HyperLogLog algorithm work?

October 16, 2022 by Tarik

The main trick behind this algorithm is that if you, observing a stream of random integers, see an integer which binary representation starts with some known prefix, there is a higher chance that the cardinality of the stream is 2^(size of the prefix). That is, in a random stream of integers, ~50% of the numbers … Read more