language: en

Hierarchical Optimization of Optimal Path Finding for Transportation Applications

Ning Jing
Changsha Institute of Technology
jning@eecs.umich.edu
Yun-Wu Huang
University of Michigan
ywh@eecs.umich.edu
Elke A. Rundensteiner
University of Michigan
rundenst@eecs.umich.edu

Abstract Efficient path query processing is a key requirement for advanced database applications including GIS (Geographic Information Systems) and ITS (Intelligent Transportation Systems). We study the problem in the context of automobile navigation systems where a large number of path requests can be submitted over the transportation network within a short period of time. To guarantee efficient re-sponsefor path queries, we employ a path view materialization strategy for precomputing the best paths. We tackle the following three issues: (1) memory-resident solutions quickly exceed current computer storage capacity for networks of thousands of nodes, (2) disk-based solutions have been found inefficient to meet the stringent performance requirements, and (3) path views become too costly to update for large graphs. We propose the HEP V (Hierarchical Encoded Path View) approach that addresses these problems while guaranteeing the optimality of path retrieval. Our experimental results reveal that HEP V is more efficient than previously known path finding approaches.

1 Introduction