Performance analysis of hierarchical shortest path algorithms

A. Fetterer, S. Shekhar

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

The shortest-path problem is an essential component of many applications including Advanced Traveler Information Systems (ATIS), computer networks, etc. A hierarchical routing algorithm decomposes the original graph into a set of fragment graphs and also into a boundary graph which summarizes the fragment graphs. A fully memoized hierarchical routing algorithm pre-computes and stores the shortest-path data structure and the shortest-path-cost data structure for the graph fragments, as well as for the boundary graph. The storage cost of the fully memoized approach can be reduced by a virtual or a hybrid memoization approach, where few or none of the relevant data structures have been pre-computed. This paper achieves two firsts. We use a real graph with 123,000 nodes and 313,000 edges, which is two orders of magnitude larger than the graphs used in related work. Second, the paper analyzes the effect of memoizing individual data structures for the storage overhead and computation time of A*-based hierarchical routing algorithms. Analysis and experiments with the Twin Cities metropolitan road-map show that memoizing the shortest-path-cost data structure for the boundary graph provides the best savings in computation time, for a given amount of storage and a small number of fragments. Memoizing the relevant part of the shortest-path-cost data structure for the fragment graphs provides the next best savings, followed by memoizing the shortest-path data structure for the boundary graph.

Original languageEnglish (US)
Pages (from-to)84-92
Number of pages9
JournalProceedings of the International Conference on Tools with Artificial Intelligence
StatePublished - Dec 1 1997

Fingerprint

Dive into the research topics of 'Performance analysis of hierarchical shortest path algorithms'. Together they form a unique fingerprint.

Cite this