Database Reference
In-Depth Information
2.2.3 Ranking Uncertain Objects
At the object level, the rank-
k
probability and
top
-k probability are defined as fol-
lows.
Definition 2.14 (Object rank-
k
probability and top-
k
probability).
For an uncer-
tain object
O
, the
object rank-
k
probability
Pr
(
,
)
O
k
is the probability that any
∈
instance
o
O
is ranked at the
k
-th position in possible worlds according to
f
, that
is
)=
o
∈
O
Pr
(
o
,
k
)
.
Pr
(
O
,
k
(2.3)
The
object top-
k
probability
Pr
k
(
O
)
is the probability that any instance in
O
is
ranked top-
k
in possible worlds, that is
k
j
=
1
Pr
(
o
,
j
)
.
Pr
k
)=
o
∈
O
Pr
k
)=
o
∈
O
(
O
(
O
(2.4)
The probabilistic ranking queries discussed in Section 2.2.2 can be applied at the
object level straightforwardly. Therefore, we skip the definitions of those queries.
2.3 Extended Uncertain Data Models and Ranking Queries
In this section, we develop three extended uncertain data models and ranking queries
on those models, to address different application interest.
2.3.1 Uncertain Data Stream Model
As illustrated in Scenario 2 of Example 1.1, the instances of an uncertain object
may keep arriving in fast pace and thus can be modeled as a data stream. The in-
stances are generated by an underlying
temporal random variable
whose distribu-
tion evolves over time. To keep our discussion simple, we assume a synchronous
model. That is, each time instant is a positive integer, and at each time instant
t
(
, an instance is collected for an uncertain data stream. To approximate the
current distribution of a temporal random variable, practically we often use the ob-
servations of the variable in a recent time window as the sample instances.
t
>
0
)
Definition 2.15 (Uncertain data stream, sliding window).
An
uncertain data stream
is a (potentially infinite) series of instances
O
=
,
,···
(
>
)
[
]
o
1
o
2
. Given a time instants
t
t
0
,
O
t
is the instance of stream
O
.
