Hierarchical optimization of optimal path finding for transportation applications

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 tmrtsportation network within a short period of time. To guarantee efficient responsefor path queries, we employ a path view materiatization strategy for precomputing the best paths. We tackle the following three issues: (1) memory-resident solutions quickly exceed cr.nrentcomputer storage capacity for networks of thousands of nodes, (2) diskbased 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 HEPV (Hierarchical Encoded Path View) approach that addressesthese problems while guaranteeing the optimality of path retrieval. Our experimental fesuks reveaf that HEPV is more efficient than previously known path finding approaches.