Database Reference
In-Depth Information
2.3.3.2 Path Queries
We formulate the probabilistic path queries on uncertain road networks.
Definition 2.22 (Probabilistic path queries).
Given probabilistic graph
G
(
V
,
E
,
W
)
,
two vertices
u
,
v
∈
V
, a weight threshold
l
>
0, and a probability threshold
τ
∈
(
0
,
1
]
,
a
probabilistic path query
Q
l
(
u
,
v
)
finds all paths
P
∈P
v
such that
F
P
(
l
)
≥
τ
.
u
,
There can be many paths between two vertices in a large graph. Often, a user is
interested in only the “best” paths and wants a ranked list. Thus, we define weight-
and probability-threshold top-
k
path queries.
Definition 2.23 (Top-
k
probabilistic path queries).
Given probabilistic graph
G
(
V
,
E
,
W
)
, two vertices
u
,
v
∈
V
, an integer
k
>
0, and a weight threshold
l
>
0,
a
weight-threshold top-
k
path query
WTQ
l
(
u
,
v
)
finds the
k
paths
P
∈P
u
,
v
with
the largest
F
P
(
values.
For a path
P
,given
probability threshold
l
)
τ
∈
(
0
,
1
]
, we can find the smallest
weight
x
such that
F
P
(
x
)
≥
τ
, which is called the
τ
-confident weight
, denoted by
F
−
1
P
(τ)=
min
{
x
|
x
∈
w
P
∧
Pr
[
w
P
≤
x
]
≥
τ
}
(2.8)
A
probability-threshold top-
k
path query
PTQ
k
τ
(
u
,
v
)
finds the
k
paths
P
∈P
u
,
v
with the smallest
F
−
1
P
(τ)
values.
Example 2.14 (Path Queries). In the probabilistic graph in Figure 2.6, there are
4
paths between A and D, namely P
1
=
A
,
B
,
D
,P
2
=
A
,
B
,
E
,
D
,P
3
=
A
,
C
,
E
,
B
,
D
,
and P
4
=
A
,
C
,
E
,
D
. Suppose the weights of all edges are independent in this ex-
ample.
Given a weight threshold l
8
, a proba-
bilistic path query Q
l
finds the paths whose weights are at most
48
of probability at
least
0
=
48
and a probability threshold
τ =
0
.
.
8
. According to the cumulative distribution functions of the paths, we have
F
P
1
(
)=
.
92
,F
P
2
(
)=
.
14
,F
P
3
(
)=
.
028
, and F
P
4
(
)=
.
48
0
48
0
48
0
48
0
492
. Thus, the
answer is
.
The weight-threshold top-
3
path query WTQ
l
(
{
P
1
}
A
,
D
)
finds the top-
3
paths P hav-
. The answer to WTQ
l
(
ing the largest
48
-weight probability values F
P
(
48
)
A
,
D
)
is
{
P
1
,
.
The probability-threshold top-
3
path query PTQ
3
P
4
,
P
2
}
τ
(
A
,
D
)
finds the top-
3
paths
8
-confidence weights F
−
1
P
P having the smallest
0
.
(
0
.
8
)
. Since F
P
1
(
40
)=
0
.
7
and
8
is
45
. Thus, F
−
1
P
1
F
P
1
(
45
)=
0
.
92
, the smallest weight that satisfies F
P
(
x
)
≥
0
.
(
0
.
8
)=
45
. Similarly, we have F
−
1
P
2
75
,F
−
1
P
3
105
, and F
−
1
P
4
(
0
.
8
)=
(
0
.
8
)=
(
0
.
8
)=
75
. There-
fore, the answer to PTQ
2
τ
(
A
,
D
)
is
{
P
1
,
P
2
,
P
4
}
.
To keep our presentation simple, in the rest of the topic, we call probabilistic path
queries, weight- and probability-threshold top-
k
queries as
path queries
,
WT top-
k
queries
, and
PT top-
k
queries
, respectively.
