Spatio-temporal Networks: Modeling, Storing, and Querying Temporally-Detailed Roadmaps - Space-Time Integration in Geography and GIScience - page 92

sub-intervals [7:30 9:29] and [9:30 10:30]. Now, we can compute the ALSP using
two runs of a DP based algorithm (George et al. 2007b ) (one on [7:30 9:29] and
another on [9:30 10:30]).
The advantages of critical time point based approaches are twofold. First, they
allow us to compress the result set of the query to a set of routes and their
corresponding time intervals instead of a single route for every start time. Second,
they are computationally more efficient since they avoid redundant re-computation
across the start-times sharing a common solution.
A key challenge in designing algorithms based on critical time points is to
minimize the amount of time needed to compute them while ensuring correct-
ness and completeness. Our preliminary work explored critical time point based
approaches for shortest path (Gunturi et al. 2011 ) and minimum spanning tree
problems (Gunturi et al. 2010 ). Preliminary results showed that these approaches
are promising, but require further research.

6.12 Physical Model of Spatio-temporal Networks

Physical models of spatio-temporal networks need to capture the possible changes
in topology and values of network parameters with time and provide the basis for
the formulation of computationally efficient and correct algorithms. In this section
we review the strengths and weaknesses.

6.13 Snapshot Partitioning

Snapshot Partitioning for spatio-temporal network storage can be represented by a
snapshot graph, such as Fig. 6.4 . Snapshot storage techniques are partitioned into
data pages using geometry (Guttman 1984 ; Samet 1995 ) or connectivity (Shekhar
and Liu 1997 ) methods. If a snapshot requires more space than a data page, it may
be decomposed into multiple data pages using techniques such as CCAM (Shekhar
and Liu 1997 ), R-Tree (Guttman 1984 ), etc. Fig. 6.9 shows a snapshot storage
approximation, with the data page partitioning visualized with dashed lines and
page numbering, using a small graph where multiple snapshots fit inside a data
page. However producing a time stamped static graph at each time step leads to
great I/O cost when executing queries such as evalRoute ( route , time )inTable 6.3
due to the need to frequently access data pages as the STN is traversed. Calling
evalRoute ( ACD ,1) requires first accessing the traversal time attribute of edge AC at
t D 1, stored on Data Page 1 in this example. Next, edge CD at t D 3 is needed
to complete the route evaluation, stored on Data Page 2. Note how the route
evaluation operation had to access two different data pages due to the snapshot-
based orthogonal partitioning.