Materialization Trade-Offs in Hierarchical Shortest Path Algorithms: A Case Study in ATIS
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Materialization Trade-Offs in Hierarchical Shortest Path Algorithms: A Case Study in ATIS
Published Date
1997
Publisher
Type
Report
Abstract
Materialization and hierarchical routing algorithms are 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 (23]. A hierarchical routing algorithm deccmposes 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 [13]. 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 n ,aterializing
inruvidual 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 shorte;t-path-cost
view for the boundary graph provides the best savings in computation time, for a given a.mcunt 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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
This work was supported by the NSF (grant number NSF/!Rl-9631539) and the Federal Highway Authority (Minnesota
Guidestar Program)
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Shekhar, Shashi; Fetterer, Andrew; Goyal, Brajesh. (1997). Materialization Trade-Offs in Hierarchical Shortest Path Algorithms: A Case Study in ATIS. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215326.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.