Spatio-temporal networks: Modeling, storing, and querying temporally-Detailed roadmaps

Given a spatial network and its variations over time (e.g., time-varying travel times on road networks) this chapter discusses how to model, query and store spatio-temporal networks. This problem has application in several domains such as transportation networks, emergency planning, knowledge discovery from sensor data, and crime analysis. Adequately representing the temporal nature of spatial networks would potentially allow us to raise interesting questions (e.g., ecorouting, non-FIFO behavior) and find efficient solutions. In transportation networks, travelers are often interested in finding the best time to start so that they spend the least time on the road. Crime data analysts may be interested in finding temporal patterns of crimes at certain locations or the routes in the network that show significantly high crime rates. Modeling the time dependence of sensor network data would certainly improve the process of discovering patterns such as hot spots. In these application domains, it is often necessary to develop a model that captures both the time dependence of the data and the underlying connectivity of the locations. There are significant challenges in developing a model for spatiotemporal networks. The model needs to balance storage efficiency and expressive power and provide adequate support for the algorithms that process the data.