-
Department Info
-
-
Admissions
-
-
Academics
-
-
People
-
-
Research
-
-
-
- Browse reports by year:
- [ ALL 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 ]
University of Minnesota - Computer Science and Engineering Technical Report Abstract
Spatio-temporal Network Databases and Routing Algorithms
Report Number: 08-039Date of Submission: 11/17/2008
Authors:
View Report:
PDF format
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.