Flajolet–Martin algorithm

The Flajolet–Martin algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for approximating the number of distinct elements in a stream with a single pass and space-consumption logarithmic in the maximal number of possible distinct elements in the stream (the <a href="/facts/Count-distinct_problem/wdCajcpa">count-distinct problem</a>). The algorithm was introduced by <a href="/facts/Philippe_Flajolet/8C9NqUlD">Philippe Flajolet</a> and G. Nigel Martin in their 1984 article "Probabilistic Counting Algorithms for Data Base Applications". Later it has been refined in "LogLog counting of large cardinalities" by Marianne Durand and <a href="/facts/Philippe_Flajolet/8C9NqUlD">Philippe Flajolet</a>, and "<a href="/facts/HyperLogLog/F4A4uA9U">HyperLogLog</a>: The analysis of a near-optimal cardinality estimation algorithm" by <a href="/facts/Philippe_Flajolet/8C9NqUlD">Philippe Flajolet</a> et al.
In their 2010 article "An optimal algorithm for the distinct elements problem", <a href="/facts/Daniel_M._Kane/kzqNSgLf">Daniel M. Kane</a>, <a href="/facts/Jelani_Nelson/uXphwn9B">Jelani Nelson</a> and <a href="/facts/David_P._Woodruff/8WFBrKE2">David P. Woodruff</a> give an improved algorithm, which uses nearly optimal space and has optimal O(1) update and reporting times.

Flajolet–Martin algorithm open-in-new

Flajolet–Martin algorithm