Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types.

Abstract

Efficient path query processing necessary for route guidance has been identified as one of the key requirements for Intelligent Transportation Systems (ITS) applications. While precomputing the view of all shortest paths provides the most efficient path retrieval, the view maintenance and storage costs become unrealistic for large ITS networks. Based on ITS road type classification, we propose a hierarchical path view approach, in which the path view maintenance and storage costs are dramatically reduced at the cost of negligible loss of path optimality. Comparing with the traditional ITS path finding approaches that use A or hierarchical A , our hierarchical approach is superior in three areas: 1) path search is more efficient, 2) the connecting point from the low-level roads to the high-level roads and vice versa are dynamically determined based on the most recent traffic, 3) within one region, the high-level traffic can be dynamically rerouted through the low-level roads. In ...