Approximate counting algorithm - Revision history

LR.127: Adding short description: "Optimization theory in computing"

2025-02-18T19:02:06Z

Adding short description: "Optimization theory in computing"

← Previous revision		Revision as of 19:02, 18 February 2025
Line 1:		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 (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.		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.

193.28.39.53: /* Algorithm */

2024-11-26T10:05:55Z

Algorithm

← Previous revision		Revision as of 10:05, 26 November 2024
Line 56:		Line 56:

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

	This can be easily achieved on a computer. Let <math>c</math> be the current value of the counter. Generating <math>c</math> pseudo-random bits and using the [[Logical conjunction\|logical AND]] of all those bits and add the result to the counter. As the result was zero if any of those pseudo-random bits are zero, achieving an increment probability of <math>2^{-c}</math>. This procedure is executed each time the request is made to increment the counter.		This can be easily achieved on a computer. Let <math>c</math> be the current value of the counter. Generating <math>c</math> pseudo-random bits and using the [[Logical conjunction\|logical AND]] of all those bits and add the result to the counter. As the result was zero if any of those pseudo-random bits are zero, achieving an increment probability of <math>2^{-c}</math>. This procedure is executed each time the request is made to increment the counter.

Citation bot: Alter: title, template type. Add: chapter. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

2023-07-21T20:21:11Z

Alter: title, template type. Add: chapter. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 20:21, 21 July 2023
Line 53:		Line 53:
	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>		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 ~~journal~~\|last1=Einziger\|first1=G.\|last2=Fellman\|first2=B.\|last3=Kassner\|first3=Y.~~\|date=April 2015~~\|title~~=Independent counter estimation buckets\|journal~~=2015 IEEE Conference on Computer Communications (INFOCOM)\|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.		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.

	==Algorithm==		==Algorithm==

Dwmalone: Use math mode for power.

2022-12-24T16:50:37Z

Use math mode for power.

← Previous revision		Revision as of 16:50, 24 December 2022
Line 48:		Line 48:
	\|}		\|}

	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 2^5, or 32. There is a fairly low probability that the actual count of increment events was 5 (<math>\frac{1}{1024} = 1 \times \frac{1}{2} \times \frac{1}{4} \times \frac{1}{8} \times \frac{1}{16}</math>). The actual count of increment events is likely to be "around 32", but it could be arbitrarily high (with decreasing probabilities for actual counts above 39).		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 fairly low probability that the actual count of increment events was 5 (<math>\frac{1}{1024} = 1 \times \frac{1}{2} \times \frac{1}{4} \times \frac{1}{8} \times \frac{1}{16}</math>). The actual count of increment events is likely to be "around 32", but it could be arbitrarily high (with decreasing probabilities for actual counts above 39).

	===Selecting counter values===		===Selecting counter values===

Dwmalone: Tidy up wording.

2022-12-24T16:49:33Z

Tidy up wording.

← Previous revision		Revision as of 16:49, 24 December 2022
Line 56:		Line 56:

	==Algorithm==		==Algorithm==
	When incrementing the counter, "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.		The algorithm can be implemented by hand. When incrementing the counter, flip a coin a number of times of the corresponding to the counter's current value. If it comes up heads each time, then increment the counter. Otherwise, do not increment it.

	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 is executed each time the request is made to increment the counter.		This can be easily achieved on a computer. Let <math>c</math> be the current value of the counter. Generating <math>c</math> pseudo-random bits and using the [[Logical conjunction\|logical AND]] of all those bits and add the result to the counter. As the result was zero if any of those pseudo-random bits are zero, achieving an increment probability of <math>2^{-c}</math>. This procedure is executed each time the request is made to increment the counter.

	==Applications==		==Applications==

Dwmalone: Neaten references a little.

2022-12-24T16:43:49Z

Neaten references a little.

← Previous revision		Revision as of 16:43, 24 December 2022
Line 70:		Line 70:

	==Sources==		==Sources==
	* Morris, R. Counting large numbers of events in small registers. Communications of the ACM 21, 10 (1978), 840–842		* Morris, R. ''Counting large numbers of events in small registers''. Communications of the ACM 21, 10 (1978), 840–842
	* Flajolet, P. Approximate Counting: A Detailed Analysis. BIT 25, (1985), 113–134 [http://algo.inria.fr/flajolet/Publications/Flajolet85c.pdf]		* Flajolet, P. ''Approximate Counting: A Detailed Analysis''. BIT 25, (1985), 113–134 [http://algo.inria.fr/flajolet/Publications/Flajolet85c.pdf]
	* ~~Michael~~ F., ~~Chung-Kuei~~ L., Prodinger, 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]		* 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:Randomized algorithms]]		[[Category:Randomized algorithms]]

Dwmalone: Slight improvement in wording.

2022-12-24T16:39:08Z

Slight improvement in wording.

← Previous revision		Revision as of 16:39, 24 December 2022
Line 6:		Line 6:
	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]].		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]].

	As an example, 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.		As an example, to increment from 4 to 8, a pseudo-random number would be generated such that the probability the counter is increased is 0.25. Otherwise, the counter remains at 4.

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

Dwmalone: Tidy up wikilink.

2022-12-24T16:36:40Z

Tidy up wikilink.

← Previous revision		Revision as of 16:36, 24 December 2022
Line 1:		Line 1:
	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 [[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.		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==		==Theory of operation==

Citation bot: Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

2022-07-03T17:32:51Z

Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

← Previous revision		Revision as of 17:32, 3 July 2022
Line 53:		Line 53:
	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>		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 journal\|~~last~~=Einziger\|~~first~~=G.\|last2=Fellman\|first2=B.\|last3=Kassner\|first3=Y.\|date=April 2015\|title=Independent counter estimation buckets\|journal=2015 IEEE Conference on Computer Communications (INFOCOM)\|pages=2560–2568\|doi=10.1109/INFOCOM.2015.7218646\|isbn=978-1-4799-8381-0}}</ref> which restrict the effect of a larger counter to the other counters in the bucket.		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 journal\|last1=Einziger\|first1=G.\|last2=Fellman\|first2=B.\|last3=Kassner\|first3=Y.\|date=April 2015\|title=Independent counter estimation buckets\|journal=2015 IEEE Conference on Computer Communications (INFOCOM)\|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.

	==Algorithm==		==Algorithm==

2A01:E34:ECD2:4CF0:FD49:70A3:47AC:5A5F at 12:42, 22 March 2021

2021-03-22T12:42:13Z

← Previous revision		Revision as of 12:42, 22 March 2021
Line 1:		Line 1:
	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 [[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 algorithms, and the more general problem of determining the frequency moments of a data stream has been central to the field.		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 [[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==		==Theory of operation==