Talk:Approximate counting algorithm - Revision history

Cewbot: Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{WikiProject Articles for creation}}, {{WikiProject Computer science}}.

2024-01-25T08:27:26Z

Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{WikiProject Articles for creation}}, {{WikiProject Computer science}}.

← Previous revision		Revision as of 08:27, 25 January 2024
Line 1:		Line 1:
	{{talkheader}}		{{talkheader}}
	{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett ~~\|class=start~~}}		{{WikiProject banner shell\|class=Start\|
			{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett }}
	{{WikiProject Computer science ~~\|class=Start~~\|importance=low}}		{{WikiProject Computer science \|importance=low}}
			}}

	== Coin tossing ==		== Coin tossing ==

Harryboyles: fixing importance parameter in {{WikiProject Computer science}}

2024-01-14T03:00:37Z

fixing importance parameter in {{WikiProject Computer science}}

← Previous revision		Revision as of 03:00, 14 January 2024
Line 1:		Line 1:
	{{talkheader}}		{{talkheader}}
	{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett \|class=start}}		{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett \|class=start}}
	{{WikiProject Computer science \|class=Start\|~~pmportance~~=low}}		{{WikiProject Computer science \|class=Start\|importance=low}}

	== Coin tossing ==		== Coin tossing ==

Rich Farmbrough: /* Coin tossing */

2018-10-17T16:52:59Z

Coin tossing

← Previous revision		Revision as of 16:52, 17 October 2018
Line 5:		Line 5:
	== Coin tossing ==		== Coin tossing ==
	Is it really necessary to toss the coin N times for a counter with value N on every event just to see if they're all heads? Couldn't we stop as soon as a tail is observed? -- [[User:Ralph Corderoy\|Ralph Corderoy]] ([[User talk:Ralph Corderoy\|talk]]) 08:28, 6 July 2011 (UTC)		Is it really necessary to toss the coin N times for a counter with value N on every event just to see if they're all heads? Couldn't we stop as soon as a tail is observed? -- [[User:Ralph Corderoy\|Ralph Corderoy]] ([[User talk:Ralph Corderoy\|talk]]) 08:28, 6 July 2011 (UTC)
			:No, you could have multiple tails. All the best: ''[[User:Rich Farmbrough\|Rich]] [[User talk:Rich Farmbrough\|Farmbrough]]'',<small> 16:52, 17 October 2018 (UTC).</small><br />

	Actually you don't need multiple tosses at all. Simply generate a random number and take it modulo 2^V, where V is the current value. If the modulo is 0, then increment the counter. --[[User:CAFxX\|CAFxX]] ([[User talk:CAFxX\|talk]]) 15:14, 4 January 2012 (UTC)		Actually you don't need multiple tosses at all. Simply generate a random number and take it modulo 2^V, where V is the current value. If the modulo is 0, then increment the counter. --[[User:CAFxX\|CAFxX]] ([[User talk:CAFxX\|talk]]) 15:14, 4 January 2012 (UTC)

			:This would be true if you knew the value. The point is that you don't, you only have the previous approximation, and knowledge that another instance has occured. Certainly if you have a run of X you might be able to optimise. All the best: ''[[User:Rich Farmbrough\|Rich]] [[User talk:Rich Farmbrough\|Farmbrough]]'',<small> 16:52, 17 October 2018 (UTC).</small><br />

	== Recent developments ==		== Recent developments ==

Dthomsen8: /* top */

2018-06-23T00:32:55Z

top

← Previous revision		Revision as of 00:32, 23 June 2018
Line 1:		Line 1:
	{{talkheader}}		{{talkheader}}
	{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett \|class=start}}{{WikiProject Computer science \|class=Start}}		{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett \|class=start}}
			{{WikiProject Computer science \|class=Start\|pmportance=low}}

	== Coin tossing ==		== Coin tossing ==

InternetArchiveBot: Notification of altered sources needing review #IABot (v1.2.5)

2016-10-16T16:58:16Z

Notification of altered sources needing review #IABot (v1.2.5)

← Previous revision		Revision as of 16:58, 16 October 2016
Line 11:		Line 11:
	Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
	http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/173.252.71.4\|173.252.71.4]] ([[User talk:173.252.71.4\|talk]]) 23:24, 22 January 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->		http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/173.252.71.4\|173.252.71.4]] ([[User talk:173.252.71.4\|talk]]) 23:24, 22 January 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

			== External links modified ==

			Hello fellow Wikipedians,

			I have just modified {{plural:1\|one external link\|1 external links}} on [[Approximate counting algorithm]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=744655753 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot\|this simple FaQ]] for additional information. I made the following changes:
			*Added archive https://web.archive.org/web/20160304042036/http://jupiter.math.nctu.edu.tw/~mfuchs/approx_count_3.pdf to http://jupiter.math.nctu.edu.tw/~mfuchs/approx_count_3.pdf

			When you have finished reviewing my changes, please set the ''checked'' parameter below to '''true''' or '''failed''' to let others know (documentation at {{tlx\|Sourcecheck}}).

			{{sourcecheck\|checked=false}}

			Cheers.—[[User:InternetArchiveBot\|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot\|Report bug]])</span> 16:58, 16 October 2016 (UTC)

Christian75: Assessment: +Computer science: class=Start (assisted)

2015-06-05T06:22:42Z

Assessment: +Computer science: class=Start (assisted)

← Previous revision		Revision as of 06:22, 5 June 2015
Line 1:		Line 1:
	{{talkheader}}		{{talkheader}}
	{{~~WPAFC~~\|ts=20081108212502\|reviewer=Graeme Bartlett\|class=start}}		{{WikiProject Articles for creation \|ts=20081108212502 \|reviewer=Graeme Bartlett \|class=start}}{{WikiProject Computer science \|class=Start}}

	== Coin tossing ==		== Coin tossing ==

SineBot: Signing comment by 173.252.71.4 - "/* Recent developments */"

2013-01-22T23:25:41Z

Signing comment by 173.252.71.4 - "Recent developments: "

← Previous revision		Revision as of 23:25, 22 January 2013
Line 10:		Line 10:

	Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
	http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm		http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/173.252.71.4\|173.252.71.4]] ([[User talk:173.252.71.4\|talk]]) 23:24, 22 January 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

173.252.71.4: /* Recent developments */

2013-01-22T23:24:35Z

Recent developments

← Previous revision		Revision as of 23:24, 22 January 2013
Line 10:		Line 10:

	Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
			http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm

SineBot: Signing comment by Herojoker - "/* Recent developments */ new section"

2012-08-26T22:44:03Z

Signing comment by Herojoker - "Recent developments: new section"

← Previous revision		Revision as of 22:44, 26 August 2012
Line 9:		Line 9:
	== Recent developments ==		== Recent developments ==

	Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included.		Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

Herojoker: /* Recent developments */ new section

2012-08-26T22:42:55Z

Recent developments: new section

← Previous revision		Revision as of 22:42, 26 August 2012
Line 6:		Line 6:

	Actually you don't need multiple tosses at all. Simply generate a random number and take it modulo 2^V, where V is the current value. If the modulo is 0, then increment the counter. --[[User:CAFxX\|CAFxX]] ([[User talk:CAFxX\|talk]]) 15:14, 4 January 2012 (UTC)		Actually you don't need multiple tosses at all. Simply generate a random number and take it modulo 2^V, where V is the current value. If the modulo is 0, then increment the counter. --[[User:CAFxX\|CAFxX]] ([[User talk:CAFxX\|talk]]) 15:14, 4 January 2012 (UTC)

			== Recent developments ==

			Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included.

← Previous revision		Revision as of 16:58, 16 October 2016
Line 11:		Line 11:
	Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		Developments like the HyperLogLog algorithm (see [http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html highscalability.com]) should perhaps be included. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Herojoker\|Herojoker]] ([[User talk:Herojoker\|talk]] • [[Special:Contributions/Herojoker\|contribs]]) 22:42, 26 August 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
	http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/173.252.71.4\|173.252.71.4]] ([[User talk:173.252.71.4\|talk]]) 23:24, 22 January 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->		http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation <= This is a great description of the algorithm <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/173.252.71.4\|173.252.71.4]] ([[User talk:173.252.71.4\|talk]]) 23:24, 22 January 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

			== External links modified ==

			Hello fellow Wikipedians,

			I have just modified {{plural:1\|one external link\|1 external links}} on [[Approximate counting algorithm]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=744655753 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot\|this simple FaQ]] for additional information. I made the following changes:
			*Added archive https://web.archive.org/web/20160304042036/http://jupiter.math.nctu.edu.tw/~mfuchs/approx_count_3.pdf to http://jupiter.math.nctu.edu.tw/~mfuchs/approx_count_3.pdf

			When you have finished reviewing my changes, please set the ''checked'' parameter below to '''true''' or '''failed''' to let others know (documentation at {{tlx\|Sourcecheck}}).

			{{sourcecheck\|checked=false}}

			Cheers.—[[User:InternetArchiveBot\|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot\|Report bug]])</span> 16:58, 16 October 2016 (UTC)