Spatio-temporal network databases and routing algorithms: A summary of results

Betsy George, Sangho Kim, Shashi Shekhar

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

59 Scopus citations

Abstract

Spatio-temporal networks are spatial networks whose topology and parameters change with time. These networks are important due to many critical applications such as emergency traffic planning and route finding services and there is an immediate need for models that support the design of efficient algorithms for computing the frequent queries on such networks. This problem is challenging due to potentially conflicting requirements of model simplicity and support for efficient algorithms. Time expanded networks which have been used to model dynamic networks employ replication of the network across time instants, resulting in high storage overhead and algorithms that are computationally expensive. In contrast, proposed time-aggregated graphs do not replicate nodes and edges across time; rather they allow the properties of edges and nodes to be modeled as a time series. Since the model does not replicate the entire graph for every instant of time, it uses less memory and the algorithms for common operations (e.g. connectivity, shortest path) are computationally more efficient than those for time expanded networks. One important query on spatio-temporal networks is the computation of shortest paths. Shortest paths can be computed either for a given start time or to find the start time and the path that leads to least travel time journeys (best start time journeys). Developing efficient algorithms for computing shortest paths in a time varying spatial network is challenging because these journeys do not always display greedy property or optimal substructure, making techniques like dynamic programming inapplicable. In this paper, we propose algorithms for shortest path computations in both contexts. We present the analytical cost models for the algorithms and provide an experimental comparison of performance with existing algorithms.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 10th International Symposium, SSTD 2007, Proceedings
Pages460-477
Number of pages18
Volume4605 LNCS
StatePublished - Dec 1 2007
Event10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007 - Boston, MA, United States
Duration: Jul 16 2007Jul 18 2007

Publication series

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

Other

Other10th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2007
CountryUnited States
CityBoston, MA
Period7/16/077/18/07

Keywords

  • Shortest paths
  • Spatio-temporal data bases
  • Time-aggregated graphs

Fingerprint Dive into the research topics of 'Spatio-temporal network databases and routing algorithms: A summary of results'. Together they form a unique fingerprint.

Cite this