Spatial Network Big Databases: Queries And Storage Methods by Kwangsoo Yang

Spatial Network Big Databases: Queries And Storage Methods

byKwangsoo Yang, Shashi Shekhar

Paperback | May 9, 2018

Pricing and Purchase Info

$174.15 online 
$193.50 list price save 9%
Earn 871 plum® points

Prices and offers may vary in store

Quantity:

In stock online

Ships free on orders over $25

Not available in stores

about

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.

Title:Spatial Network Big Databases: Queries And Storage MethodsFormat:PaperbackDimensions:101 pages, 9.41 X 7.24 X 0.98 inPublished:May 9, 2018Publisher:Springer NatureLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:3319859641

ISBN - 13:9783319859644

Appropriate for ages: All ages

Look for similar items by category:

Table of Contents

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