Streaming algorithm - Revision history

Andy02124: Resolving Category:Harv and Sfn no-target errors: add Flajolet/Martin

2025-03-08T17:48:42Z

Resolving Category:Harv and Sfn no-target errors: add Flajolet/Martin

← Previous revision		Revision as of 17:48, 8 March 2025
Line 289:		Line 289:
	\| pages = 20–29\| title-link=Symposium on Theory of Computing \| citeseerx=10.1.1.131.4984 \| s2cid=1627911 }}.		\| pages = 20–29\| title-link=Symposium on Theory of Computing \| citeseerx=10.1.1.131.4984 \| s2cid=1627911 }}.
	* {{citation \| contribution = Models and issues in data stream systems \| last1 = Babcock \| first1 = Brian \| last2 = Babu \| first2 = Shivnath \| last3 = Datar \| first3 = Mayur \| last4 = Motwani \| first4 = Rajeev \| author4-link = Rajeev Motwani \| last5 = Widom \| first5 = Jennifer \| author5-link = Jennifer Widom \| url = http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf \| doi = 10.1145/543613.543615 \| pages = 1–16 \| title = Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) \| year = 2002 \| isbn = 978-1581135077 \| citeseerx = 10.1.1.138.190 \| s2cid = 2071130 \| access-date = 2013-07-15 \| archive-date = 2017-07-09 \| archive-url = https://web.archive.org/web/20170709081550/http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf \| url-status = dead }}.		* {{citation \| contribution = Models and issues in data stream systems \| last1 = Babcock \| first1 = Brian \| last2 = Babu \| first2 = Shivnath \| last3 = Datar \| first3 = Mayur \| last4 = Motwani \| first4 = Rajeev \| author4-link = Rajeev Motwani \| last5 = Widom \| first5 = Jennifer \| author5-link = Jennifer Widom \| url = http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf \| doi = 10.1145/543613.543615 \| pages = 1–16 \| title = Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) \| year = 2002 \| isbn = 978-1581135077 \| citeseerx = 10.1.1.138.190 \| s2cid = 2071130 \| access-date = 2013-07-15 \| archive-date = 2017-07-09 \| archive-url = https://web.archive.org/web/20170709081550/http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf \| url-status = dead }}.
			* {{Cite journal \|doi=10.1016/0022-0000(85)90041-8 \|title=Probabilistic counting algorithms for data base applications \|journal=Journal of Computer and System Sciences \|volume=31 \|issue=2 \|pages=182–209 \|year=1985 \|last1=Flajolet \|first1=Philippe \|last2=Martin \|first2=G. Nigel \|url=http://algo.inria.fr/flajolet/Publications/FlMa85.pdf \|access-date=2016-12-11}}
	* {{citation		* {{citation
	\| title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries		\| title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries

David Eppstein: Deeper undo to restore unreferenced section tag

2025-03-08T17:12:22Z

Deeper undo to restore unreferenced section tag

← Previous revision		Revision as of 17:12, 8 March 2025
Line 67:		Line 67:

	== Evaluation ==		== Evaluation ==
			{{unreferenced section\|date=April 2021}}
	The performance of an algorithm that operates on data streams is measured by three basic factors:		The performance of an algorithm that operates on data streams is measured by three basic factors:
	* The number of passes the algorithm must make over the stream.		* The number of passes the algorithm must make over the stream.

TedTed: /* Evaluation */ remove irrelevant promotional sentence

2025-03-08T09:16:32Z

Evaluation: remove irrelevant promotional sentence

← Previous revision		Revision as of 09:16, 8 March 2025
Line 67:		Line 67:

	== Evaluation ==		== Evaluation ==
	CricFy TV<ref>{{cite web \|last1=Wiliam \|first1=Jordan \|title=CricFy TV \|url=https://cricfyhd.com/ \|website=cricfyhd.com \|publisher=howdy \|access-date=March 3, 2025}}</ref> and CricFree TV are two separate live streaming apps.
	The performance of an algorithm that operates on data streams is measured by three basic factors:		The performance of an algorithm that operates on data streams is measured by three basic factors:
	* The number of passes the algorithm must make over the stream.		* The number of passes the algorithm must make over the stream.

Ira Leviton: Fixed a reference. Please see Category:CS1 errors: dates.

2025-03-02T20:24:52Z

Fixed a reference. Please see Category:CS1 errors: dates.

← Previous revision		Revision as of 20:24, 2 March 2025
Line 67:		Line 67:

	== Evaluation ==		== Evaluation ==
	CricFy TV<ref>{{cite web \|last1=~~wiliam~~ \|first1=~~jordan~~ \|title=CricFy TV \|url=https://cricfyhd.com/ \|website=cricfyhd.com \|publisher=howdy \|access-date=~~03/03/~~2025}}</ref> and CricFree TV are two separate live streaming apps.		CricFy TV<ref>{{cite web \|last1=Wiliam \|first1=Jordan \|title=CricFy TV \|url=https://cricfyhd.com/ \|website=cricfyhd.com \|publisher=howdy \|access-date=March 3, 2025}}</ref> and CricFree TV are two separate live streaming apps.
	The performance of an algorithm that operates on data streams is measured by three basic factors:		The performance of an algorithm that operates on data streams is measured by three basic factors:
	* The number of passes the algorithm must make over the stream.		* The number of passes the algorithm must make over the stream.

Wiliamjordan: why CricFy tv is important for SEO.

2025-03-02T20:21:18Z

why CricFy tv is important for SEO.

← Previous revision		Revision as of 20:21, 2 March 2025
Line 67:		Line 67:

	== Evaluation ==		== Evaluation ==
	CricFy TV<ref>{{cite web \|last1=wiliam \|first1=jordan \|title=~~Editing~~ ~~Live Streaming~~ \|url=https://cricfyhd.com/ \|website=cricfyhd.com \|publisher=howdy \|access-date=03/03/2025}}</ref> and CricFree TV are two separate live streaming apps.		CricFy TV<ref>{{cite web \|last1=wiliam \|first1=jordan \|title=CricFy TV \|url=https://cricfyhd.com/ \|website=cricfyhd.com \|publisher=howdy \|access-date=03/03/2025}}</ref> and CricFree TV are two separate live streaming apps.
	The performance of an algorithm that operates on data streams is measured by three basic factors:		The performance of an algorithm that operates on data streams is measured by three basic factors:
	* The number of passes the algorithm must make over the stream.		* The number of passes the algorithm must make over the stream.

Wiliamjordan: why CricFy tv is important for SEO.

2025-03-02T20:19:39Z

why CricFy tv is important for SEO.

← Previous revision		Revision as of 20:19, 2 March 2025
Line 67:		Line 67:

	== Evaluation ==		== Evaluation ==
			CricFy TV<ref>{{cite web \|last1=wiliam \|first1=jordan \|title=Editing Live Streaming \|url=https://cricfyhd.com/ \|website=cricfyhd.com \|publisher=howdy \|access-date=03/03/2025}}</ref> and CricFree TV are two separate live streaming apps.
	{{unreferenced section\|date=April 2021}}
	The performance of an algorithm that operates on data streams is measured by three basic factors:		The performance of an algorithm that operates on data streams is measured by three basic factors:
	* The number of passes the algorithm must make over the stream.		* The number of passes the algorithm must make over the stream.

Retimuko: Undid revision 1273782776 by 85.64.234.68 (talk) we don't rely on self-published sources

2025-02-04T06:05:37Z

Undid revision 1273782776 by 85.64.234.68 (talk) we don't rely on self-published sources

← Previous revision		Revision as of 06:05, 4 February 2025
Line 194:		Line 194:
	The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.		The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.

	This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>~~. Their algorithm was eventually proven optimal by Braverman and Zamir <ref>https://arxiv.org/abs/2411.02148</ref>.~~		This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>

	===Frequent elements===		===Frequent elements===

85.64.234.68: Appears correct nonetheless. Undid revision 1273303525 by Retimuko (talk)

2025-02-04T00:34:15Z

Appears correct nonetheless. Undid revision 1273303525 by Retimuko (talk)

← Previous revision		Revision as of 00:34, 4 February 2025
Line 194:		Line 194:
	The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.		The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.

	This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>		This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>. Their algorithm was eventually proven optimal by Braverman and Zamir <ref>https://arxiv.org/abs/2411.02148</ref>.

	===Frequent elements===		===Frequent elements===

Retimuko: Undid revision 1273238546 by 85.64.234.68 (talk) self-published

2025-02-01T18:13:26Z

Undid revision 1273238546 by 85.64.234.68 (talk) self-published

← Previous revision		Revision as of 18:13, 1 February 2025
Line 194:		Line 194:
	The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.		The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.

	This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>~~. Their algorithm was eventually proven optimal by Braverman and Zamir <ref>https://arxiv.org/abs/2411.02148</ref>.~~		This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>

	===Frequent elements===		===Frequent elements===

85.64.234.68: /* Simpler approach to calculate {{math|F2}} */

2025-02-01T12:07:56Z

Simpler approach to calculate {{math|F2}}

← Previous revision		Revision as of 12:07, 1 February 2025
Line 194:		Line 194:
	The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.		The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.

	This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>		This further reduces the complexity to calculate <math>F_2</math> to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>. Their algorithm was eventually proven optimal by Braverman and Zamir <ref>https://arxiv.org/abs/2411.02148</ref>.

	===Frequent elements===		===Frequent elements===