Difference between revisions of "Open Problems:6"
(Created page with "{{DISPLAYTITLE:Problem 6: Filtering Irrelevant Data}} {{Infobox |label1 = Proposed by |data1 = Sariel Har-Peled |label2 = Source |data2 = Kanpur 2006...") |
|||
| (2 intermediate revisions by the same user not shown) | |||
| 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. | 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. | ||
Latest revision as of 01:38, 7 March 2013
| Suggested by | Sariel Har-Peled |
|---|---|
| Source | Kanpur 2006 |
| Short link | https://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 [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.
