Ajouter à une liste

Librairie Eyrolles - Paris 5e
Indisponible

Spatial Network Big Databases

Kwangsoo yang (author)|shashi shekhar (author)

101 pages, parution le 23/04/2017

Ajouter à une liste

Indisponible

Résumé

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

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

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.

1st Edition 2017th editionIllustrationsQA76.9.B45Big data.|Databases.|Database searching.1SwitzerlandChamKwangSoo Yang, Shashi Shekhar.

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Kwangsoo yang (author)\|shashi shekhar (author)
Parution	23/04/2017
Nb. de pages	101
Format	155 x 235
Poids	344g
EAN13	9783319566566

Avantages Eyrolles.com

Livraison à partir de 0,01 € en France métropolitaine

Paiement en ligne SÉCURISÉ

Livraison dans le monde

Retour sous 15 jours

+ d'un million et demi de livres disponibles

Spatial Network Big Databases

Résumé

Caractéristiques techniques

Consultez aussi