Materialization trade-offs in hierarchical shortest path algorithms

Shashi Shekhar, Andrew Fetterer, Brajesh Goyal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial Databases - 5th International Symposium, SSD 1997, Proceedings
Pages94-111
Number of pages18
DOIs
StatePublished - 1997
Event5th International Symposium on Spatial Databases, SSD 1997 - Berlin, Germany
Duration: Jul 15 1997Jul 18 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1262 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Symposium on Spatial Databases, SSD 1997
CountryGermany
CityBerlin
Period7/15/977/18/97

Fingerprint Dive into the research topics of 'Materialization trade-offs in hierarchical shortest path algorithms'. Together they form a unique fingerprint.

Cite this