Materialization trade-offs in hierarchical shortest path algorithms

Materialization and hierarchical routing algorithms axe becoming important tools in querying databases for the shortest paths in time-critical applications like Intelligent Transportation Systems (ITS), due to the growing size of their spatial graph databases [16]. A hierarchical routing algorithm decomposes the original graph into a set of fragment graphs and a boundary graph which summarizes the fragment graphs. A fully materialized hierarchical routing algorithm pre-computes and stores the shortest-path view and the shortest-path-cost view for the graph fragments as well as for the boundary graph [9]. The storage cost of the fully materialized approach can be reduced by a virtual or a hybrid materialization approach, where few or none of the relevant views are pre-computed. This paper explores the effect of materializing individual views for the storage overhead and computation time of hierarchical routing algorithms. Our experiments with the Twin Cities metropolitan road-map show that materializing the shortest-path-cost view for the boundary graph provides the best savings in computation time, for a given amount of storage and a small number of fragments. Materializing the relevant part of the shortest-path-cost view for the fragment graphs provides the next best savings, followed by materializing the shortest-path view for the boundary graph. Virtual shortest-path-view on fragments can reduce storage costs by an order of magnitude or more for large graphs.