The Algorithm with the Best Name - HyperLogLog Explained #SoME1

Here are some of the resources used for this video: ** Erratum ** - What HyperLogLog uses is not the harmonic mean of L1 to Ln, but the harmonic mean of 2^(L1), ..., 2^(Ln). *** Original papers *** Durand, Marianne; Flajolet, Philippe (2003). “Loglog Counting of Large Cardinalities” Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" *** Industry Blog Posts *** https://redditblog.com/2017/05/24/view-counting-at-reddit/ https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/ https://research.google/pubs/pub40671/ *** Useful Blog Posts and Lectures *** PS: The Flajolet-Martin counter uses a similar idea but *is not* based on the longest streak of 0's. Although the blog post in Towards Datascience says so at the beginning of the bost, they admit by the end that it was only for simplicity's sake. https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/ https://towardsdatascience.com/hyperloglog-a-simple-but-powerful-algorithm-for-data-scientists-aed50fe47869 https://arpitbhayani.me/blogs/flajolet-martin Slides from prof. Robert Sedgwick: https://www.cs.princeton.edu/~rs/talks/AC11-Cardinality.pdf *** Songs *** PS: All songs were taken from EpidemicSound - Pitch and Pull - Moins Le Quartet - Paris After Dark - Moins Le Quartet