Hyperloglog

I will be talking about Hyperloglog, a cardinality (i.e. number of distinct elements) estimation algorithm. In general, counting the number of elements in a set gets harder as the number of sets increase. For e.g., you might want to count number of users from a country.. i.e. number of sets is just 200+ and you can use a map of country to count. But, if you want to count the number of unique visitors to a popular website, then the number of sets become really large.

Probabilistic counting methods give a way to estimate the cardinality of sets without keeping track of every single item. Hyperloglog is probably the best known of those methods.

Paper: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf