Difference between revisions of "Open Problems:73"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Krzysztof Onak moved page Waiting:73 to Open Problems:73 without leaving a redirect: Moving to main list of problems)
(Updating header)
Line 1: Line 1:
|title=Streaming online algorithms
|who=Edo Liberty
|who=Edo Liberty

Latest revision as of 18:43, 18 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, however, 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].