Krzysztof Onak: updating header

2013-03-07T01:42:41Z

updating header

Krzysztof Onak at 05:13, 16 November 2012

2012-11-16T05:13:07Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 20: Relations between Streaming Models}} {{Infobox |label1 = Proposed by |data1 = Christian Sohler |label2 = Source |data2 = [[Workshops:Kanpur_2006|Kan..."

2012-10-16T15:20:57Z

Created page with "{{DISPLAYTITLE:Problem 20: Relations between Streaming Models}} {{Infobox |label1 = Proposed by |data1 = Christian Sohler |label2 = Source |data2 = [[Workshops:Kanpur_2006|Kan..."

New page

{{DISPLAYTITLE:Problem 20: Relations between Streaming Models}}
{{Infobox
|label1 = Proposed by
|data1 = Christian Sohler
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/20
}}
There are many different models for data streaming. For example, in
geometry we have the insertion-only model, insertion/deletion model, and
the sliding window model. In the insertion-only model we are given
a stream of points $p_1,\dots, p_n$. In the insertion/deletion model
the stream consists of '''Insert'''$(p)$ and '''Delete'''$(p)$ operations
and is assumed to be valid in the sense that no point is deleted
that has not been previously inserted and no point is inserted twice.
In the sliding window model we get a stream $p_1,\ldots,p_m$ but we
are only interested in the $n$ most recent points.

How do these models relate to each other? Obviously, any algorithm
for the insertion/deletion model is also an algorithm in the insertion-only model. Under which assumptions is the opposite true
as well? Is there any relation between the insertion/deletion model
and the sliding window model? The models are not equivalent since
one can obtain an exact algorithm for the sum of points (centroid)
under the insertion/deletion model but only a $(1+\epsilon)$-approximation
in the sliding window model. Is it possible to prove that (under
reasonable assumptions) these two models are equivalent within
a certain approximation factor, i.e., if there is an $\alpha$-approximation
algorithm in one model then there is a $(c \alpha)$-approximation
algorithm in the other model?

Since the above questions are quite general and may be difficult
to answer, here is one that may be easier to solve:
Can you prove that the reset model {{cite|HoffmannMR-04}} is
equivalent to uniform sampling?

In the reset model we have a stream of
updates $(i,p)$ telling that the new position of point number $i$ is $p$. The conjecture is that the reset model is equivalent to
uniform random sampling. Since one direction is immediate, one has to
prove that any algorithm in the reset model can be turned into a
streaming algorithm that initially chooses a set of points (indices) uniformly at random and tracks the positions of these points. Then
the algorithm computes its output based on the position of these
points.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Christian Sohler

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 20: Relations between Streaming Models}}
+{{Header
-{{Infobox
+|title=Relations between Streaming Models
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Christian Sohler
+|who=Christian Sohler
 }}
 There are many different models for data streaming. For example, in

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

Open Problems:20 - Revision history

Krzysztof Onak: updating header

Krzysztof Onak at 05:13, 16 November 2012

Krzysztof Onak: 1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 20: Relations between Streaming Models}} {{Infobox |label1 = Proposed by |data1 = Christian Sohler |label2 = Source |data2 = [[Workshops:Kanpur_2006|Kan..."