Problem 6: Filtering Irrelevant Data

From Open Problems in Sublinear Algorithms
Revision as of 09:12, 1 October 2012 by Krzysztof Onak (talk | contribs) (Created page with "{{DISPLAYTITLE:Problem 6: Filtering Irrelevant Data}} {{Infobox |label1 = Proposed by |data1 = Sariel Har-Peled |label2 = Source |data2 = Kanpur 2006...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Proposed by Sariel Har-Peled
Source Kanpur 2006
Short link 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 [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.