Database Reference
In-Depth Information
t
B
∈
B
may be the instance of multiple objects
{
t
A
1
,···,
t
A
d
}
, where
t
A
i
is a tuple in
A
with linkage
(
t
A
i
,
t
B
)
∈L
(1
≤
i
≤
d
). A mutual exclusion rule
R
t
B
=(
t
A
i
,
t
B
)
⊕
···⊕
(
specifies that
t
B
should only belong to one object in a possible
world. Alternatively, we can consider each tuple
t
B
∈
t
A
d
,
t
B
)
B
as an uncertain object
and a tuple
t
A
∈
.
We develop a probabilistic mutual exclusion graph (PME-graph) to describe the
dependencies among objects in the probabilistic linkage model. The PME-graph
is shown to be a special form of Markov random fields. Answering ranking
queries on probabilistic linkages is significantly different from that on indepen-
dent uncertain objects. We propose efficient query evaluation methods that are
verified to be efficient and scalable by experimental results.
A
is an instance of
t
B
if there is a linkage
(
t
A
,
t
B
)
∈L
•
Last, we extend the ranking uncertain data problem to more complicated data
types: uncertain road networks. An uncertain road network is a simple graph, for
each edge, the weight is an uncertain object containing a set of instances. As a
result, the weight of any path in an uncertain network is also an uncertain object.
We propose three types of probabilistic path queries.
-
A
probabilistic path query
with a weight threshold
w
and a probability thresh-
old
p
finds the paths between two end vertices whose weights are at most
l
with a probability of at least
p
.
-
Given a path
P
and a weight constraint
l
, the
l
-weight probability is the proba-
bility that
P
's weight is at most
l
.A
weight-threshold top-k path query
returns
the paths between two end vertices whose
l
-weight probabilities are the high-
est.
-
Given a certain probability threshold
p
, we can find, for each path, the small-
est weight achievable with a probability of at least
p
. This is called the
p
-
confidence weight of the path. A
probability-threshold top-k path query
finds
the paths whose
p
-confidence weights are the smallest.
Each type of path queries finds its edge in real applications. To answer those
queries efficiently, we address two major challenges. First, we propose three effi-
cient methods to compute
l
-weight probabilities and
p
-confidence weights. Then,
we develop two path search methods that find the paths satisfying the query effi-
ciently.
9.2 Future Directions: Possible Direct Extensions
It is interesting to extend the ranking queries and their evaluation methods developed
in this topic to other related uncertain data models and queries. Some of them are
listed below.
