Database Reference
In-Depth Information
Ertl [154] considered the geographical location of each edge in a traffic network
and associated with each edge a radius, indicating how important the edge is in path
search. An edge is only considered for a path if either the start vertex or the end
vertex is inside the radius of the edge.
In [155], a hierarchical traffic network is proposed based on graph partitioning.
When the shortest path search is far away from the start or end vertices, the algo-
rithm only looks at the paths at higher levels of the hierarchical network.
In [156, 157], a concept of “transit” node is introduced to preprocess traffic net-
works. A transit node is on a set of non-local shortest paths. The distance from every
vertex in the network to its closest transit node is computed to help the shortest path
search.
In [158], important driving and speed patterns are mined from historical data, and
are used to help to compute the fastest paths on traffic networks. A road hierarchy
is built based on different classes of roads. Frequently traversed road segments are
preferred in the path search.
In addition, Kurzhanski and Varaiya [159] considered a model that allows corre-
lations between links for the reachability problem. More studies on the hierarchical
approach for searching shortest path include [160, 161, 162, 163].
3.7.2.1 How Is Our Study Related?
The above studies tackle the path queries in large scale certain traffic networks.
Therefore, both the graph models and the query types are different from our work.
Thus, those techniques cannot be extended to probabilistic path queries on uncertain
road networks.
Moreover, although hierarchical indices have been extensively used in path
queries on certain traffic networks, the existing index techniques only work for cer-
tain path queries. Thus, we develop a hierarchical partition tree to index the weight
probability distributions on graphs.
