Spatio-temporal Network Databases and Routing Algorithms: A Summary of ResultsIntroductionAn Illustrative Application DomainBroad ChallengesScope and Outline of the PaperBasic ConceptsThe Conceptual ModelShortest Path Computation for Time Aggregated Graphs (SP-TAG Algorithm)Case Study: Best Start Time Shortest PathsBEst Start Time Shortest Path (BEST) AlgorithmExperimental AnalysisExperimental Results and AnlaysisConclusions and Future WorkSpatio-temporal Network Databases andRouting Algorithms: A Summary of ResultsBetsy George, Sangho Kim, and Shashi ShekharDepartment of Computer Science and Engineering, University of Minnesota200 Union St SE, Minneapolis, MN 55455, USA{bgeorge,sangho,shekhar}@cs.umn.eduhttp://www.spatial.cs.umn.edu/Abstract. Spatio-temporal networks are spatial networks whose topol-ogy and parameters change with time. These networks are important dueto many critical applications such as emergency traffic planning and routefinding services and there is an immediate need for models that supportthe design of efficient algorithms for computing the frequent queries onsuch networks. This problem is challenging due to potentially conflictingrequirements of model simplicity and support for efficient algorithms.Time expanded networks which have been used to model dynamic net-works employ replication of the network across time instants, resultingin high storage overhead and algorithms that are computationally ex-pensive. In contrast, proposed time-aggregated graphs do not replicatenodes and edges across time; rather they allow the properties of edges andnodes to be modeled as a time series. Since the model does not replicatethe entire graph for every instant of time, it uses less memory and thealgorithms for common operations (e.g. connectivity, shortest path) arecomputationally more efficient than those for time expanded networks.One important query on spatio-temporal networks is the computation ofshortest paths. Shortest paths can be computed either for a given starttime or to find the start time and the path that leads to least traveltime journeys (best start time journeys). Developing efficient algorithmsfor computing shortest paths in a time varying spatial network is chal-lenging because these journeys do not always display greedy propertyor optimal substructure, making techniques like dynamic programminginapplicable. In this paper, we propose algorithms for shortest path com-putations in both contexts. We present the analytical cost models for thealgorithms and provide an experimental comparison of performance withexisting algorithms.Keywords: time-aggregated graphs, shortest paths, spatio-temporaldata bases.1 IntroductionThe underlying data of interest for many significant applications such as trans-portation networks is structured as a spatio-temporal network, which consistsCorresponding author.D. Papadias, D. Zhang, and G. Kollios (Eds.): SSTD 2007, LNCS 4605, pp. 460–477, 2007.c Springer-Verlag Berlin Heidelberg 2007Spatio-temporal Network Databases and Routing Algorithms 461of a finite collection of points (i.e. nodes) with location information, the line-segments (i.e. edges) connecting the points, and the time-varying attributes at-tached to the elements. For example, a spatio-temporal network database for atraveler’s trip planning may store the intersections as nodes, the road segmentsas edges, and time dependent travel time attached to the road segments. In thecase of evacuation planning, time dependent capacity may be added to the roadsegments as another important attribute.Related work in the field of databases falls into three broad categories (1)Spa-tial network databases, (2) Graph Databases, and (3) Spatio-temporal databases.The recent release of Oracle (version 10g) includes a network data model tostore and maintain the connectivity of link-node networks and supports basicfeatures such as shortest path [14]. The Network Analyst extension of ArcMapfrom ESRI supports a network geodatabase and provides basic algorithms (e.g.,shortest path, service area, closest facility, etc.) [7]. However, these products donot address the time variance of spatial networks, which is crucial in applicationssuch as route computations and emergency planning.Graph databases [5,6,7,19,22,24] also primarily deal with spatial networksthat do not vary with time. Research in graph databases that accounts for tem-poral variations perform computations over a snapshot of the network [4,9,18],and does not consider the interplay between the edge travel times and the ex-istence of edges. For example, Ding [4] proposed a model that addresses thetime-dependency by associating a temporal attribute to every edge and node ofthe network so that its state at any instant of time can be retrieved. This modelperforms path computations over a snapshot of the network. Since the networkcan change over the time taken to traverse these paths, this computation mightnot give realistic solutions. The model does not propose an algorithm for theleast travel time paths.Although the need for live traffic information is increasing, there has been lit-tle work on the modeling and algorithms for spatio-temporal network databases.Chorochronos [12], studied various aspects of spatio-temporal databases includ-ing ontology, modeling, and implementation. However, the researchers have yetto study spatio-temporal networks in this framework.Research in Operations Research is based on the time expanded network[10,11,13,15,17,21]. This model duplicates the original network for each discretetime unit t =0, 1,...,T where T represents the extent of the time horizon. Theexpanded network has edges connecting a node and its copy at the next instantin addition to the edges in the original network, replicated for every time in-stant. This significantly increases the network size and is very expensive withrespect to memory. Because of the increased problem size due to replication ofthe network, the computations become expensive.As the first step towards the study of spatio-temporal network databases,we previously proposed a spatio-temporal network model named the time ag-gregated graph [8]. In this paper, we introduce a case study of this model usingrouting algorithms. The proposed algorithms (SP-TAG and BEST) compute theshortest path in the given network for a given start time at the source node and462 B. George, S. Kim, and S. Shekharthe least travel time route over the entire time period. The proposed