Open Problems:6 - Revision history

Krzysztof Onak at 01:38, 7 March 2013

2013-03-07T01:38:51Z

Krzysztof Onak at 04:58, 16 November 2012

2012-11-16T04:58:51Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 6: Filtering Irrelevant Data}} {{Infobox |label1 = Proposed by |data1 = Sariel Har-Peled |label2 = Source |data2 = Kanpur 2006..."

2012-10-01T09:12:02Z

Created page with "{{DISPLAYTITLE:Problem 6: Filtering Irrelevant Data}} {{Infobox |label1 = Proposed by |data1 = Sariel Har-Peled |label2 = Source |data2 = Kanpur 2006..."

New page

{{DISPLAYTITLE:Problem 6: Filtering Irrelevant Data}}
{{Infobox
|label1 = Proposed by
|data1 = Sariel Har-Peled
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/6
}}
For many problems most of the stream is irrelevant and a good use of a streaming algorithm could be to filter out the irrelevant parts of the stream such that the data left is small enough to be processed by an I/O efficient algorithm. How effective can a small-space algorithm be at such filtering for a given problem? An alternative idea that addresses similar issues is to allow a data stream algorithm to delete and annotate the stream and take multiple passes as in {{cite|DemetrescuFR-06}}. If the deletion of irrelevant elements was a large component of the algorithm then it would not make sense to measure the total number of passes taken by the algorithm but, rather, the total number of elements processed.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Sariel Har-Peled
 }}
 For many problems most of the stream is irrelevant and a good use of a streaming algorithm could be to filter out the irrelevant parts of the stream such that the data left is small enough to be processed by an I/O efficient algorithm. How effective can a small-space algorithm be at such filtering for a given problem? An alternative idea that addresses similar issues is to allow a data stream algorithm to delete and annotate the stream and take multiple passes as in {{cite|DemetrescuFR-06}}. If the deletion of irrelevant elements was a large component of the algorithm then it would not make sense to measure the total number of passes taken by the algorithm but, rather, the total number of elements processed.

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