Database Reference
In-Depth Information
distribution in
, where x min and x max are the minimal and maximal weights
in the original road network. The results in Figures 8.12(a) and (b) are similar. All
three algorithms are scalable, and the hierarchical approximation algorithms has
a very short runtime (20 seconds on the largest data set, the North America Road
Network ( NA ) with 175
[
x min ,
x max ]
,
812 nodes). Although constructing the HP-tree takes around
2
,
000 seconds in this case, it is constructed only once offline.
8.5 Summary
In this chapter, we studied the problem of answering probabilistic path queries de-
fined in Section 2.3.3. There are two major challenges for efficient query evaluation.
First, given a path P and a weight threshold l , how can we compute the l -weight
probability of P efficiently? Second, given an uncertain road network and a proba-
bilistic path query, how can we search for the paths satisfying the query efficiently?
To solve the first challenge, we developed three methods for efficient l -weight
probability calculation: an exact algorithm, a constant factor approximation method
and a sampling based approach.
To address the second challenge, we proposed two path search methods.
A depth-first search algorithm enhanced by effective pruning techniques was de-
veloped.
P* algorithm, a best first search method, was devised to search for all paths satis-
fying the query. It uses a heuristic method to estimate the l -weight probabilities
of the unexplored paths and prune the paths whose estimated l -weight proba-
bilities fail the threshold. Although being an heuristic method, it guarantees to
find all paths in the exact solution, since the estimated l -weight probabilities are
always no smaller than the actual l -weight probabilities.
An extensive empirical evaluation verified the effectiveness and efficiency of the
probabilistic path queries and our methods.
Search WWH ::




Custom Search