Spatial Network Big Databases: Queries and Storage Methods

by Kwangsoo Yang

1 Spatial Network Big 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

116 pages, Paperback

Published April 17, 2017