Approximate counting algorithm: Difference between revisions

Revision as of 17:44, 11 May 2009

Latest revision as of 19:02, 18 February 2025

(38 intermediate revisions by 26 users not shown)

Line 1:

{{Short description|Optimization theory in computing}}

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 of [[Bell Labs]], it uses [[randomized algorithm|probabilistic techniques]] to increment the [[counter]].

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)|Robert Morris]] of [[Bell Labs]], it uses [[randomized algorithm|probabilistic techniques]] to increment the [[Counter (digital)|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. When focused on high quality of approximation and low probability of failure, [[Jelani Nelson|Nelson]] and Yu showed that a very slight modification to the Morris Counter is asymptotically optimal amongst all algorithms for the problem.<ref name=ny2020>{{cite journal | last1=Nelson | first1=Jelani | last2 = Yu | first2 = Huacheng | year=2020 | title=Optimal bounds for approximate counting | arxiv=2010.02116 }} </ref> The algorithm is considered one of the precursors of [[Streaming algorithm|streaming algorithms]], and the more general problem of determining the frequency moments of a data stream has been central to the field.

== Theory of operation ==

Using Morris' algorithm, the counter represents an "[[order of magnitude]] estimate" of the actual count. The approximation is mathematically [[Unbiased_estimatorUnbiased estimator|unbiased]].

To increment the counter, a [[pseudo-random]] event is used, such that the incrementing is a probabilistic event. To save space, only the exponent is kept. For example, in base 2, the counter can estimate the count to be 1, 2, 4, 8, 16, 32, and all of the [[powers of two]]. The memory requirement is simply to hold the [[exponent]].

Using Morris' algorithm, the counter represents an "[[order of magnitude]] estimate" of the actual count. The approximation is mathematically [[Unbiased_estimator|unbiased]].

InAs orderan example, to increment thefrom counter4 to 8, a [[pseudo-random]] eventnumber iswould used,be generated such that the incrementingprobability isthe acounter probabilistic event. In order to save space, only theis exponentincreased is kept0.25. For example, in base 2Otherwise, the counter canremains estimate the count to be 1, 2,at 4, 8, 16, 32, and all of the [[powers of two]]. The memory requirement is simply to hold the [[exponent]].

As an example, in order to increment from 4 to 8, a pseudo-random number would be generated such that a probability of .25 generates a positive change in the counter. Otherwise, the counter remains at 4.

The table below illustrates some of the potential values of the counter:

Line 13:

{| class="wikitable" border="1"

|-

! Stored Binarybinary Valuevalue of Countercounter

! Approximation

! Range of Possiblepossible Valuesvalues for the Actualactual Countcount

! Expectation (sufficiently large n, uniform distribution)

|-

| 0

| 1

| 0, or initial value

| exactly 1

| 0

|-

| 1

| 2

| 21 or more

| 2

|-

| 10

| 4

| 32 or more

| 6

|-

| 11

| 8

| 43 or more

| 14

|-

| 100

| 16

| 54 or more

| 30

|-

| 101

| 32

| 65 or more

| 62

|}

If the counter holds the value of 101, which equates to an exponent of 5 (the decimal equivalent of 101), then the estimated count is <math>2^5</math>, or 32. There is a veryfairly low probability that the actual count of increment events was 65 (which<math>\frac{1}{1024} would= imply1 that an\times extremely\frac{1}{2} rare\times event\frac{1}{4} occurred with the pseudo-random number generator, the same probability as getting 10 consecutive heads\times in\frac{1}{8} 10 coin\times flips\frac{1}{16}</math>). The actual count of increment events is likely to be "around 32", but it could be infinitelyarbitrarily high (with decreasing probabilities for actual counts above 3239).

===Selecting counter values===

== Algorithm ==

While using powers of 2 as counter values is memory efficient, arbitrary values tend to create a dynamic error range, and the smaller values will have a greater error ratio than bigger values. Other methods of selecting counter values consider parameters such as memory availability, desired error ratio, or counting range to provide an optimal set of values.<ref>Tsidon, Erez, Iddo Hanniel, and Isaac Keslassy. "Estimators also need shared values to grow together." INFOCOM, 2012 Proceedings IEEE. IEEE, 2012.</ref>

However, when several counters share the same values, values are optimized according to the counter with the largest counting range, and produce sub-optimal accuracy for smaller counters. Mitigation is achieved by maintaining Independent Counter Estimation buckets,<ref>{{Cite book|last1=Einziger|first1=G.|last2=Fellman|first2=B.|last3=Kassner|first3=Y.|title=2015 IEEE Conference on Computer Communications (INFOCOM) |chapter=Independent counter estimation buckets |date=April 2015|pages=2560–2568|doi=10.1109/INFOCOM.2015.7218646|isbn=978-1-4799-8381-0|s2cid=15673730 }}</ref> which restrict the effect of a larger counter to the other counters in the bucket.

When incrementing the counter, simply "flip a coin" the number of times of the counter's current value. If it comes up "Heads" each time, then increment the counter. Otherwise, do not increment it.

== Algorithm ==

This can be done programmatically by generating "c" pseudo-random bits (where "c" is the current value of the counter), and using the logical AND function on all of those bits. The result is a zero if any of those pseudo-random bits are zero, and a one if they are all ones. Simply add the result to the counter. This procedure should be executed each time the request is made to increment the counter.

The algorithm can be implemented by hand. When incrementing the counter, simply "flip a coin" thea number of times ofcorresponding to the counter's current value. If it comes up "Heads"heads each time, then increment the counter. Otherwise, do not increment it.

This can be doneeasily programmaticallyachieved byon generatinga "c"computer. pseudo-randomLet bits (where "<math>c"</math> isbe the current value of the counter),. Generating <math>c</math> pseudo-random bits and using the [[Logical conjunction|logical AND]] function onof all of those bits and add the result to the counter. As Thethe result is awas zero if any of those pseudo-random bits are zero, andachieving aan oneincrement ifprobability theyof are all ones. Simply add the result to the counter<math>2^{-c}</math>. This procedure should beis executed each time the request is made to increment the counter.

== Applications ==

== 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.

==See Sources also==

* [[HyperLogLog]]

==References==

{{Reflist}}

==Sources==

* Morris, R. ''Counting large numbers of events in small registers''. Communications of the ACM 21, 10 (19771978), 840–842

* Flajolet, P. ''Approximate Counting: A Detailed Analysis''. BIT 25, (1985), 113-134113–134 [http://algo.inria.fr/flajolet/Publications/Flajolet85c.pdf]

* Fouchs, M., Lee, C-K., Prodinger, H., ''Approximate Counting via the Poisson-Laplace-Mellin Method'' [https://web.archive.org/web/20160304042036/http://jupiter.math.nctu.edu.tw/~mfuchs/approx_count_3.pdf]

[[Category:AlgorithmsRandomized algorithms]]