Geography Reference
In-Depth Information
6.15
Lagrangian Partitioning
The Lagrangian-Connectivity Partitioning (LCP) method optimizes disk storage
based upon traversal across spatio-temporal networks. Data is stored using the sub-
node record design, allowing for non-orthogonal temporal information to be stored
on a data page.
By representing a spatio-temporal network as a modified time-expanded graph,
focusing on Lagrangian connections between nodes (movement edges), a min-
cut graph partitioning (Abou-Rjeili and Karypis 2006 ) algorithm creates partitions
clustering nodes by minimizing the cuts of these movement edges. This results in
LCP collocating connected spatio-temporal nodes together on data pages, stored as
sub-node records. We propose LCP will result in more efficient I/O when using STN
operators from Table 6.3 or queries composed of them.
To illustrate, we call the route evaluation operation evalRoute(ACD,1) on each of
the partitioning methods. With orthogonal partitioning, Snapshot or Longitudinal,
whenever an edge is traversed, (e.g., A 1to C 3and C 3to D 4), a disk I/O is needed
to retrieve the data page containing the record for the next node. However, with
Lagrangian-Connectivity Partitioning, traversing from node A 1to C 3andthen C 3
to D 4 requires only one data page as all relevant sub-node records are collocated on
the same data page.
Figure 6.11 c illustrates the results of LCP applied to the same input STN as in
the other orthogonal partitioning methods. A min-cut partitioning was run on the
modified time-expanded graph (wait edges are removed to emphasize Lagrangian
connectivity) and then stored as sub-nodes on four data pages. For efficiency, we
used a bulk load operation, which sorts these statements along the block number
and inserts them into data pages. Physically, sub-node data records are stored in
data pages and a B C tree index is created to support retrieve operations.
6.16
Case Study: Evacuation Route Planning
Efficient tools are needed to identify routes and schedules to evacuate affected
populations to safety in the event of natural disasters. Hurricane Rita and the
recent tsunami revealed limitations of traditional approaches to provide emergency
preparedness for evacuees and to predict the effects of evacuation route planning.
Challenges arise during evacuations due to the spread of people over space and
time and the multiple paths that can be taken to reach them; key assumptions such
as stationary ranking of alternative routes and optimal substructure are violated
in such situations. Algorithms for evacuation route planning were first developed
by researchers in operations research and transportation science. However, these
proved to have high computational complexity and did not scale well to large
Search WWH ::




Custom Search