Introduces an overview of Spatial Network Big Database Systems, including concepts related to data modeling, query processing, and storage methods
Describes basic network algorithms that are used to design efficient spatial network query processing mechanisms
Formulates the problem of query processing and storage methods and explores new algorithms that minimize the cost of data processing
This book provides a collection of concepts, algorithms, and techniques that effectively harness the power of Spatial Network Big Data. Reading this book is a first step towards understanding the immense challenges and novel applications of SNBD database systems. This book explores these challenges via investigating scalable graph-based query processing strategies and I/O efficient storage and access methods. This book will be of benefit to academics, researchers, engineers with a particular interest in network database models, network query processing, and physical storage models.
1 Spatial Network Big Database: An Introduction . . . . . . . . . . . . . . . . . . . 1
1.1 Spatial Network Big Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Spatial Network Big Database Management Systems . . . . . . . . . . . . . 2
1.4 Computational Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Basic Graph Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 A Brief Introduction to Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Network Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Node-Node Adjacency Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Node-Edge Incidence Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Adjacency List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.4 Forward Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Single-Source Shortest Path (SSSP) . . . . . . . . . . . . . . . . . . . . . 13
2.3.2 All-Pairs Shortest Paths (APSP) . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Block Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Maximum Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.1 Augmenting-Path Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.2 Push-Relabel Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Bipartite Weighted Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Graph Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Capacity Constrained Network Voronoi Diagram . . . . . . . . . . . . . . . . . . 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.3 Problem Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
ix
x Contents
3.1.5 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Algorithms for CCNVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1 Pressure Equalizer (PE) Algorithm . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 PE-BTCC Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.3 PE-Minor Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Case Study with Brooklyn, NY road network . . . . . . . . . . . . . . . . . . . 43
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Distance-Constrained k Spatial Sub-Networks . . . . . . . . . . . . . . . . . . . . . 47
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.3 Problem Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.5 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Algorithm for RSG-NND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3 Case Study with Chicago, IL road network . . . . . . . . . . . . . . . . . . . . . 54
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Evacuation Route Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.1 Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.4 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 Algorithms for ERP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.1 Capacity Constrained Route Planner Algorithm . . . . . . . . . . . 60
5.2.2 Dartboard Network Cuts for Evacuation Route Planning
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Experimental Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3.1 Experiment Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.3.2 Experimental Results and Analysis . . . . . . . . . . . . . . . . . . . . . 69
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6 Storage Scheme for Spatio-temporal Network Datasets . . . . . . . . . . . . . 73
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1.1 Application Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1.2 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.1.3 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.1.4 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.1.5 Outline of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2 Lagrangian-Connectivity Partitioning (LCP) Approaches for SSTN. 79
Contents xi
6.2.1 LCP-G1S for LGetOneSuccessor() . . . . . . . . . . . . . . . . . . . . . 79
6.2.2 LCP-G?S for LGetAllSuccessors() . . . . . . . . . . . . . . . . . . . . . 82
6.2.3 Algorithm for LCP-G?S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3 Cost Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4 Experimental Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.4.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.4.2 Experimental Results and Analysis . . . . . . . . . . . . . . . . . . . . . 92
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.0.1 Capacity Constrained Network Voronoi Diagram. . . . . . . . . . 99
7.0.2 Distance-Constrained k Spatial Sub-Networks . . . . . . . . . . . . 100
7.0.3 Evacuation Route Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.0.4 Storage Scheme for Spatio-temporal Network Datasets . . . . . 100
"Spatial network big data (SNBD) can be widely found in every corner of modern society. Examples include temporally detailed road maps that provide car speeds every minute for every road segment and GPS trace data from our cell phones. ... The topic of this book is attractive and beneficial to readers and researchers who are interested in spatial networks, graph data, big data, and databases. It includes a clear structure when introducing the basic information, existing methods, and practical applications.” (Feng Yu, Computing Reviews, January, 4, 2018)
This book provides a collection of concepts, algorithms, and techniques that effectively harness the power of Spatial Network Big Data. Reading this book is a first step towards understanding the immense challenges and novel applications of SNBD database systems. This book explores these challenges via investigating scalable graph-based query processing strategies and I/O efficient storage and access methods. This book will be of benefit to academics, researchers, engineers with a particular interest in network database models, network query processing, and physical storage models.
1. Spatial Network Big Databases: An Introduction.- 2. Basic Graph Algorithms.- 3. Capacity Constrained Network Voronoi Diagrams.- 4. Distance-Constrained k Spatial Sub-Networks.- 5. Evacuation Route Planning.- 6. Storage Schemes for Spatio-temporal Network Datasets.- 7. Summary.
"Spatial network big data (SNBD) can be widely found in every corner of modern society. Examples include temporally detailed road maps that provide car speeds every minute for every road segment and GPS trace data from our cell phones. ... The topic of this book is attractive and beneficial to readers and researchers who are interested in spatial networks, graph data, big data, and databases. It includes a clear structure when introducing the basic information, existing methods, and practical applications." (Feng Yu, Computing Reviews, January, 4, 2018)
