Difference between revisions of "Open Problems:73"
(Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Edo Liberty }} The open problem will appear here.") |
|||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |title= | + | |title=Streaming online algorithms |
|source=baltimore16 | |source=baltimore16 | ||
|who=Edo Liberty | |who=Edo Liberty | ||
}} | }} | ||
| − | + | A tad more open-ended than the usual open problems from this website, this one arises from the following observation. While streaming algorithms are often motivated by the constraints due to "big data," in practice this data is not ''static'': however, most streaming algorithms use the structure and regularities encountered in the stream to compute solutions or results only available at the end of the streaming, in hindsight. | |
| + | |||
| + | In practice, howver, one often needs to be ''online'' as well: that is, to maintain a "good as of now" solution as the stream goes, and to combine the usual memory constraints of the streaming setting with the objectives of the standard online analysis setting. (Note that, in contrast to the majority of the machine learning literature, one cannot in general make the assumption of stochasticity; the performance thus has to be compared in the adversarial setting, or an intermediate, better suited model has to be developed.) | ||
| + | |||
| + | '''Question:''' which model can capture this real-world need for a combination of streaming and online competitivity constraints, and what algorithms can then one obtain in this model? | ||
| + | |||
| + | '''Note:''' for some work in this direction, one can consult {{cite|LibertySS-16}}. | ||
Revision as of 01:58, 12 January 2016
| Suggested by | Edo Liberty |
|---|---|
| Source | Baltimore 2016 |
| Short link | https://sublinear.info/73 |
A tad more open-ended than the usual open problems from this website, this one arises from the following observation. While streaming algorithms are often motivated by the constraints due to "big data," in practice this data is not static: however, most streaming algorithms use the structure and regularities encountered in the stream to compute solutions or results only available at the end of the streaming, in hindsight.
In practice, howver, one often needs to be online as well: that is, to maintain a "good as of now" solution as the stream goes, and to combine the usual memory constraints of the streaming setting with the objectives of the standard online analysis setting. (Note that, in contrast to the majority of the machine learning literature, one cannot in general make the assumption of stochasticity; the performance thus has to be compared in the adversarial setting, or an intermediate, better suited model has to be developed.)
Question: which model can capture this real-world need for a combination of streaming and online competitivity constraints, and what algorithms can then one obtain in this model?
Note: for some work in this direction, one can consult [LibertySS-16].
