Open Problems:13 - Revision history

Krzysztof Onak: updating header

2013-03-07T01:41:00Z

updating header

Krzysztof Onak at 05:08, 16 November 2012

2012-11-16T05:08:04Z

Krzysztof Onak at 05:07, 16 November 2012

2012-11-16T05:07:51Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 13: Effects of Subsampling}} {{Infobox |label1 = Proposed by |data1 = Yossi Matias |label2 = Source |data2 = Kanpur 2006 |labe..."

2012-10-01T19:38:55Z

Created page with "{{DISPLAYTITLE:Problem 13: Effects of Subsampling}} {{Infobox |label1 = Proposed by |data1 = Yossi Matias |label2 = Source |data2 = Kanpur 2006 |labe..."

New page

{{DISPLAYTITLE:Problem 13: Effects of Subsampling}}
{{Infobox
|label1 = Proposed by
|data1 = Yossi Matias
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/13
}}
When processing very fast streams, it is not feasible to run a streaming algorithm on the entire stream, even one that can process each element in $O(1)$ time. Rather it is necessary to sample from the stream and to process the sub-stream using a streaming algorithm. For standard problems such as estimating $F_0$, how does the sub-sampling affect that the accuracy of the streaming algorithms? How should the sampling rate and the per-element time-complexity of a streaming algorithm be traded-off to achieve optimal results?

Another way to formalize this question, suggested by Muthukrishnan, is
in terms of what part of the stream to skip and which to stream.
A formal definition of the model and algorithms for estimating $F_2$ and others can be found in
{{cite|BhattacharyyaMMY-07}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Yossi Matias

@@ Line 3: / Line 3: @@
 |source=kanpur06
 |who=Yossi Matias
 }}
 When processing very fast streams, it is not feasible to run a streaming algorithm on the entire stream, even one that can process each element in $O(1)$ time. Rather it is necessary to sample from the stream and to process the sub-stream using a streaming algorithm. For standard problems such as estimating $F_0$, how does the sub-sampling affect that the accuracy of the streaming algorithms? How should the sampling rate and the per-element time-complexity of a streaming algorithm be traded-off to achieve optimal results?

← Older revision		Revision as of 05:07, 16 November 2012
Line 1:		Line 1:
		+	{{Header
		+	\|title=Effects of Subsampling
		+	\|source=kanpur06
		+	\|who=Yossi Matias
		+	}}
		+
		+
	{{DISPLAYTITLE:Problem 13: Effects of Subsampling}}		{{DISPLAYTITLE:Problem 13: Effects of Subsampling}}
	{{Infobox		{{Infobox

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)