Approximate Counting Algorithm

The approximate counting algorithm allows the counting of a large number of events using a small amount of memory. Invented in 1977 by Robert Morris (cryptographer) of Bell Labs, it uses probabilistic techniques to increment the counter. It was fully analyzed in the early 1980s by Philippe Flajolet of INRIA Rocquencourt, who coined the name Approximate Counting, and strongly contributed to its recognition among the research community. The algorithm is considered one of the precursors of streaming algorithms, and the more general problem of determining the frequency moments of a data stream has been central to the field.

Read more about Approximate Counting AlgorithmTheory of Operation, Algorithm, Applications

Other articles related to "approximate counting algorithm":

Approximate Counting Algorithm - Applications
... The algorithm is useful in examining large data streams for patterns ... This is particularly useful in applications of data compression, sight and sound recognition, and other artificial intelligence applications ...

Famous quotes containing the words approximate and/or counting:

    the dull thunder of approximate words.
    Thom Gunn (b. 1929)

    Love is sinister,
    is mean to us in separation;
    makes our thin bodies thinner.
    This fellow Death
    lacks mercy
    and is good at counting our days.
    And Master,
    you, too, are subject
    to the plague of jealousy
    so think:
    how could womenfolk,
    soft as sprouts,
    live like this?
    Amaru (c. seventh century A.D.)