Database Reference
In-Depth Information
A sliding window W t
ω
is a selection operator defined as W t
ω (
O
)= {
O
[
i
] | (
t
ω) <
i
0 is called the width of the window.
For a set of uncertain data streams
t
}
, where
ω >
, sliding window W t
O = {
O 1 ,···,
O n }
ω ( O )=
W t
{
ω (
O i ) |
1
i
n
}
.
2.3.1.1 Connections with the Uncertain Object Model
The distribution of an uncertain data stream O in a given sliding window W t
ω
is
static. Thus, the set of instances W t
can be considered as an uncertain object.
The membership probabilities for instances depend on how the instances are gener-
ated from the underlying random variable of W t
ω (
O
)
. For example, if the instances
are drawn using simple random sampling [34], then all instances take the same prob-
ability
ω (
O
)
1
ω
. On the other hand, using other techniques like particle filtering [35] can
generate instances with different membership probabilities. In this topic, we assume
that the membership probabilities of all instances are identical. Some of our devel-
oped methods can also handle the case of different membership probabilities, which
will be discussed in Section 6.5.
Definition 2.16 (Uncertain object in a sliding window). Let O be an uncertain
data stream. At time instant t
0, the set of instances of O in a sliding window W t
ω
>
is an uncertain object denoted by W t
W t
ω (
O
)(
1
i
n
)
, where each instant o
ω (
O
)
1
ω
has the membership probability Pr
(
o
)=
.
In this topic, we assume that the distributions of uncertain data streams are inde-
pendent from each other. Handling correlations among uncertain data streams is an
important direction that we plan to investigate as future study that will be discussed
in Section 6.5. The uncertain data in a sliding window carries the possible worlds
semantics.
Definition 2.17 (Possible worlds of uncertain data streams). Let
O = {
,...,
}
O 1
O n
be a set of uncertain data streams. A possible world w
= {
v 1
,...,
}
v n
in a sliding
window W t
ω
is a set of instances such that one instance is taken from the uncertain
object of each stream in W t
ω
W t
, i.e., v i
ω (
O i
)(
1
i
n
)
. The existence probability
n
i = 1 Pr ( v i )=
n
i = 1
1
ω = ω n .
The complete set of possible worlds of sliding window W t
of w is Pr
(
w
)=
ω ( O )
is denoted by
W t
W (
ω ( O ))
.
Corollary 2.4 (Number of possible worlds). For a set of uncertain data streams
O = {
and a sliding windowW t
O 1
,...,
}
ω ( O )
O n
, the total number of possible worlds
n
is
|W (
W ω (
t
)) | = ω
.
W t
and W t
When it is clear from the context, we write
W (
ω ( O ))
as
W
ω ( O )
as W
or W t
for the sake of simplicity.
 
Search WWH ::




Custom Search