Spatio-temporal Network Databases and Routing Algorithms

Abstract

Spatio-temporal networks are spatial networks whose topology and parameters change with time. These networks are important for 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 the 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, the proposed time-aggregated graph (TAG) does not replicate nodes and edges across time; rather it allows 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. Developing efficient algorithms for computing shortest paths in a time varying spatial network is challenging because these journeys do not always display the optimal substructure, making techniques like dynamic programming inapplicable. In addition, 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). In this paper, we present algorithms for shortest path computations in both contexts using the proposed TAG and arrival time series transformation (ATST). We present the analytical cost models for the algorithms and provide an experimental comparison of performance with existing algorithms.