Database Reference
In-Depth Information
Since weights are positive, as more edges are added into a path, the
l
-weight
probability of the path decreases. Therefore, during the search, if the current path
does not satisfy the query, then all its super paths should not be searched, as they
cannot be in the answer set.
Lemma 8.4 (Monotonicity).
Given a path P and its subpath P
, and a weight
threshold l
>
0
,F
P
(
l
)
≤
F
P
(
l
)
.
(
∑
P
∈P
C
(
))
The overall complexity of the depth-first path search algorithm is
O
P
,
where
is the cost of the
l
-weight probabil-
ity calculation. If the exact method is used, then
C
P
is the set of visited paths and
C
(
P
)
(
P
)=
∏
e
∈
P
|
w
e
|
. If the bucket
approximation method is used, then
C
(
P
)=
4
t
×
∑
e
∈
P
|
w
e
|
, where
t
is the bucket
parameter. If the sampling method is used, then
C
(
P
)=
|
S
|×|
P
|
, where
|
S
|
is the
number of samples and
is the number of edges in
P
.
The method can be extended to answer top-
k
path queries as following. To answer
a WT top-
k
path query, the probability threshold
|
P
|
is set to 0 at the beginning. Once
a path between
u
and
v
is found, we compute its
l
-weight probability, and add the
path to a buffer. If the buffer contains
k
paths, we set
τ
to the smallest
l
-weight
probability of the paths in the buffer. During the search, when a new path is found
between
u
and
v
and satisfying the threshold
τ
, it is added into the buffer. At the
same time, the path in the buffer with the smallest
l
-weight probability is removed
from the buffer.
τ
is updated accordingly. Therefore, during the search, the buffer
always contains at most
k
paths. At the end of the search, the
k
paths in the buffer
are returned.
A PT top-
k
path query can be answered following the similar procedure. We set
the weight threshold
l
τ
at the beginning. During the search, a buffer always
stores at most
k
found paths between
u
and
v
with the smallest
=+∞
τ
-confident weights.
l
is set to the value of the smallest
-confident weight of the paths in the buffer. The
k
paths in the buffer at the end of the search are returned as the answers.
Limited by space, hereafter, we focus on answering probabilistic path queries
and omit the details for top-
k
path query evaluation.
τ
8.2 P*: A Best First Search Method
Although the approximation algorithms presented in Section 8.1 to accelerate the
probability calculation, it is still computationally challenging to search for all paths
in real road networks. In this section, we present the
P* algorithm
, a best first search
algorithm for efficient probabilistic path query evaluation
P* carries the similar spirit as the A* algorithm [150, 151]. It visits the vertex
that is most likely to be an answer path using a heuristic evaluation function, and
stops when the rest unexplored paths have no potential to satisfy the query. However,
the two algorithms are critically different due to the different types of graphs and
queries.
