Preface
Given the increasing proliferation of location enabled sensors, we are able to
collect a wide variety of data which has spatio-temporal semantics. Many of these
datasets have network semantics as well. For instance, traffic sensors on urban road
networks enable us to collect data on traffic signal delays and traffic congestion.
Sample upcoming datasets from these sensors include temporally detailed (TD)
roadmaps which provide typical travel speeds experienced on every road segment
for thousands of departure-times in a typical week. Likewise, we have temporally
detailed (TD) social networks that contain a temporal trace of social interactions
among the individuals in the network over a time window. These datasets can
have huge societal impact. For instance, a 2011 McKinsey Global Institute report
estimates that location-aware data could save consumers hundreds of billions of
dollars by helping vehicles avoid traffic congestion via next-generation routing
services such as eco-routing.
However, data generated on spatio-temporal graphs (STGs) presents significant
challenges for the current computer science state of the art. First, they some-
times violate the cost function decomposability assumption of current conceptual
models for representing and querying STGs. Second, they may also violate the
stationary-ranking (of candidate solutions) assumption of dynamic programming
based techniques such as Dijkstra’s shortest path algorithm. This monograph
discusses potential solutions to both these problems.
We start this monograph with a gentle introduction to STGs in Chap. 1.This
chapter discusses few potential application domains for STGs. In Chap. 2,a
discussion of some fundamental concepts underlying data is presented. A clear
understanding of these concepts is important to ensure semantic correctness of the
query results. Chapter 3 presents some representational models and data structures
for STGs. Additionally, this chapter also presents a solution to the challenge
of non-decomposability mentioned in the previous paragraph. Following this, in
Chap. 4, we discuss several algorithms for computing the fastest path for a single
departure-time. In addition, we also present an algorithm to compute betweenness
centrality on STGs. Chapters 5 and 6 discuss few advanced routing-related concepts
relating to STGs. In these chapters, we introduce the idea of critical-time-point
v
