Editing Open Problems:13
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 2: | Line 2: | ||
|source=kanpur06 | |source=kanpur06 | ||
|who=Yossi Matias | |who=Yossi Matias | ||
| + | }} | ||
| + | |||
| + | |||
| + | {{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? | 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? | ||
