Spatial Network Big Databases: Queries and Storage Methods

1 Spatial Network Big Database: An Introduction . . . . . . . . . . . . . . . . . . . 11.1 Spatial Network Big Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Spatial Network Big Database Management Systems . . . . . . . . . . . . . 21.4 Computational Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Basic Graph Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1 A Brief Introduction to Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Network Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.1 Node-Node Adjacency Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.2 Node-Edge Incidence Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.3 Adjacency List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.4 Forward Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3.1 Single-Source Shortest Path (SSSP) . . . . . . . . . . . . . . . . . . . . . 132.3.2 All-Pairs Shortest Paths (APSP) . . . . . . . . . . . . . . . . . . . . . . . . 152.4 Block Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5 Maximum Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.5.1 Augmenting-Path Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 172.5.2 Push-Relabel Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.6 Bipartite Weighted Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.7 Graph Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Capacity Constrained Network Voronoi Diagram . . . . . . . . . . . . . . . . . . 273.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.1.1 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.1.3 Problem Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31ixx Contents3.1.5 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2 Algorithms for CCNVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2.1 Pressure Equalizer (PE) Algorithm . . . . . . . . . . . . . . . . . . . . . 333.2.2 PE-BTCC Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2.3 PE-Minor Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3 Case Study with Brooklyn, NY road network . . . . . . . . . . . . . . . . . . . 433.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 Distance-Constrained k Spatial Sub-Networks . . . . . . . . . . . . . . . . . . . . . 474.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1.1 Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.1.3 Problem Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.5 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.2 Algorithm for RSG-NND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.3 Case Study with Chicago, IL road network . . . . . . . . . . . . . . . . . . . . . 544.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555 Evacuation Route Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.1.1 Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.1.3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.1.4 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.2 Algorithms for ERP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.2.1 Capacity Constrained Route Planner Algorithm . . . . . . . . . . . 605.2.2 Dartboard Network Cuts for Evacuation Route PlanningAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625.3 Experimental Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.3.1 Experiment Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685.3.2 Experimental Results and Analysis . . . . . . . . . . . . . . . . . . . . . 695.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716 Storage Scheme for Spatio-temporal Network Datasets . . . . . . . . . . . . . 736.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.1.1 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.1.2 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746.1.3 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776.1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.1.5 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.2 Lagrangian-Connectivity Partitioning (LCP) Approaches for SSTN. 79Contents xi6.2.1 LCP-G1S for LGetOneSuccessor() . . . . . . . . . . . . . . . . . . . . . 796.2.2 LCP-G S for LGetAllSuccessors() . . . . . . . . . . . . . . . . . . . . . 826.2.3 Algorithm for LCP-G S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 876.3 Cost Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896.4 Experimental Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906.4.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916.4.2 Experimental Results and Analysis . . . . . . . . . . . . . . . . . . . . . 926.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 967 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.0.1 Capacity Constrained Network Voronoi Diagram. . . . . . . . . . 997.0.2 Distance-Constrained k Spatial Sub-Networks . . . . . . . . . . . . 1007.0.3 Evacuation Route Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007.0.4 Storage Scheme for Spatio-temporal Network Datasets . . . . . 100