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

1 1 1 1 2 1 1 1

Node
A

B C

1 2 2 2

Node
B

D

1 1 1 1

Node
C

D

Node
D

Secondary Index

Data File (Disk Pages)

Fig. 6.10 Longitudinal storage of a STN

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 node-based orthogonal
partitioning. CCAM (Shekhar and Liu 1997 ) did not consider STNs, however, it
uses node-centric storage techniques. Therefore, if CCAM was applied to a spatio-
temporal network, it may end up with a storage method resembling Longitudinal
Partitioning due to the long time series characteristic of STNs causing node-centric
storage to fill entire data pages with a single node's information.
The orthogonal approaches such as Snapshot and Longitudinal do not capture the
movement access patterns inherent in the route evaluation operation. This may be
formalized via a Lagrangian frame of reference (Herrera and Bayen 2009 ) attached
to a user moving through space over time. For example, evaluation of route ACD
at different start times will retrieve the following subsets of edges: ( AC at t D 1,
CD at t D 3), ( AC at t D 2, CD at t D 3), ( AC at t D 3, CD at t D 4),etc.Note
that these groups are not orthogonal. Our proposed use of a Lagrangian frame of
reference in our approach intends to move toward capturing such non-orthogonal
access patterns.