Кратко про HyperLogLog (подробности и визуализаторы в ссылках). \(F_k\)-момент (\(F_k = \sum_i f_i^k\)). Алгоритм AMS для \(F_2\)-момента. Выбор случайного элемента из потока. Оценка для \(\sum_i g(f_i)\) при \(g(0) = 0\). Алгоритм для \(F_k\) момента.

Источники:

• The space complexity of approximating the frequency moments, Noga Alon, Yossi Matias, Mario Szegedy, 2002
• Loglog Counting of Large Cardinalities, Marianne Durand and Philippe Flajolet, 2003
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, Philippe Flajolet, Eric Fusy, Olivier Gandouet, Frederic Meunier, 2007
• http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/
• http://research.neustar.biz/2013/04/02/sketch-of-the-day-probabilistic-counting-with-stochastic-averaging-pcsa/
• http://research.neustar.biz/2012/07/09/sketch-of-the-day-k-minimum-values/
• Как HyperLogLog реализован в Redis: http://antirez.com/news/75