Spatial Network Big Databases: Queries and Storage Methods

ISBN-13: 9783319859644 / Angielski / Miękka / 2018 / 101 str.

Kwangsoo Yang; Shashi Shekhar

Recenzje

"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)

Spis treści

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