6 ms·
HyperLogLog in Practice: Algorithmic Engineering of Cardinality Estimation
- ot 14y agoAmong other things, HyperLogLog was used in the recent computation of Facebook's average diameter ("Four degrees of separation" [1]). In this paper Google squeezes out every last bit of precision, using tables to correct the bias and specialized algorithms for small cardinalities. It is an outstanding effort, I guess they use these counters everywhere. [1] http://arxiv.org/abs/1111.4570 http://arxiv.org/abs/1111.4570