Approximate counting algorithm

<p>The approximate counting algorithm allows the counting of a large number of events using a small amount of memory.  Invented in 1977 by <a href="/facts/Robert_Morris_(cryptographer)/3L0QovBu">Robert Morris</a> of <a href="/facts/Bell_Labs/fKP5Gk0H">Bell Labs</a>, it uses <a href="/facts/Randomized_algorithm/Fngl1zgk">probabilistic techniques</a> to increment the <a href="/facts/Counter_(digital)/SD2V8R8w">counter</a>.  It was fully analyzed in the early 1980s by <a href="/facts/Philippe_Flajolet/8C9NqUlD">Philippe Flajolet</a> of <a href="/facts/INRIA/ruIkcapf">INRIA</a> Rocquencourt, who coined the name approximate counting, and strongly contributed to its recognition among the research community. When focused on high quality of approximation and low probability of failure, <a href="/facts/Jelani_Nelson/uXphwn9B">Nelson</a> and Yu showed that a very slight modification to the Morris Counter is asymptotically optimal amongst all algorithms for the problem. The algorithm is considered one of the precursors of <a href="/facts/Streaming_algorithm/BjSCe5rR">streaming algorithms</a>, and the more general problem of determining the frequency moments of a data stream has been central to the field.
</p>

Approximate counting algorithm open-in-new

Approximate counting algorithm