Database Reference
In-Depth Information
Chapter 8
Probabilistic Path Queries on Road Networks
Path queries such as “find the shortest path in travel time from my hotel to the
airport” are heavily used in many applications of road networks. Currently, simple
statistic aggregates such as the average travel time between two vertices are often
used to answer path queries. However, such simple aggregates often cannot capture
the uncertainty inherent in traffic.
To capture the uncertainty in traffic such as the travel time between two vertices,
in Section 2.3.3, we modeled the weight of an edge as an uncertain object that
contains a set of samples. Moreover, we proposed three novel types of probabilistic
path queries.
•
A
probabilistic path query
asks a question such as “what are the paths from my
hotel to the airport whose travel time is at most 30 minutes with a probability of
at least 90%?”
•
A
weight-threshold top-k path query
asks a question like “what are the top-3
paths from my hotel to the airport with the highest probabilities to take at most
30 minutes?”
•
A
probability-threshold top-k path query
asks a question like “in terms of the
travel time of a path guaranteed by a probability of at least 90%, what are the
top-3 shortest paths from my hotel to the airport?”
To evaluate probabilistic path queries efficiently, in this chapter, we first develop
three efficient probability calculation methods: an exact algorithm, a constant fac-
tor approximation method and a sampling based approach. Moreover, we devise
the P* algorithm, a best-first search method based on a novel hierarchical partition
tree index and three effective heuristic estimate functions. An extensive empirical
study using real road networks and synthetic data sets shows the effectiveness of the
proposed path queries and the efficiency of the query evaluation methods.
185
