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

Secondary Index

Disk Page 1 Disk Page 2

A A

A

A

2 1

1 1 1 1

1

1

B

B

C B C B

C

C

1 1 2 1

2 1

2 1

D D

D

D

Time = 1

Time = 2 Time = 3 Time = 4

Data File (Disk Pages)

Fig. 6.9 Snapshot storage of a STN

As the name suggests, the snapshot family described in Table 6.1 is best
represented with the snapshot model. Answering questions about current or past
locations of objects are trivial. The model can easily show a network state at any
point in time, but information such as trajectory of a person or aggregate information
on a edge or node are less obvious.

6.14 Longitudinal Partitioning

Longitudinal Partitioning for a spatio-temporal network is based on the adjacency-
list main memory storage structure used by (Ahuja et al. 1993 ;Georgeetal.
2008 ). Each node is stored with its attribute information and all outgoing edges and
their attribute information. This orthogonal storage solution, as shown in Fig. 6.10 ,
suffers from the increasing disk I/O to evaluate routes in spatio-temporal networks
using operators such as evalRoute ( route , time )inTable 6.3 . This example network
has a short time series compared to its graph size, allowing multiple node records
(with adjacency list) to fit inside a data page. If the time-series length was larger
then the node record could become larger than a data page, that node record may be
split into multiple pages. This is due to the long time series being stored with each
node, resulting in a small number of nodes to be stored on each data page. Calling
evalRoute ( ACD ,1) requires first accessing the traversal time attribute of edge AC at