Spatial Network Big Databases

Queries and Storage Methods

verfasst von: KwangSoo Yang, Shashi Shekhar

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Spatial Network Big Databases: An Introduction

Abstract

This chapter provides an overview of Spatial Network Big Database Systems, including concepts related to data modeling, query processing, and storage methods. We begin with a brief description of SNBDS and present the computational challenges.

KwangSoo Yang, Shashi Shekhar

Chapter 2. Basic Graph Algorithms

Abstract

Spatial network queries are used in a wide range of applications, such as road networks, power cables, air transportation, etc. In this chapter, we describe basic network algorithms that are used to design efficient spatial network query processing mechanisms. We start by introducing the basic terminology of the graph theory that will be used in this book. Then we present multiple ways to represent network datasets, followed by a study of network algorithms.

KwangSoo Yang, Shashi Shekhar

Chapter 3. Capacity Constrained Network Voronoi Diagrams

Abstract

Network Voronoi Diagrams (NVD) are currently used in various spatial analysis applications, such as finding nearest points of interest. In this chapter, we introduce a special case of NVD, namely the Capacity Constrained Network-Voronoi Diagram (CCNVD) and explore techniques for creating this diagram. Given a graph and a set of service center nodes, a Capacity Constrained Network-Voronoi Diagram partitions the graph into a set of contiguous service areas that meet service center capacities and minimize the sum of the shortest distances from graph-nodes to allotted service centers. The CCNVD problem is important for critical societal applications such as assigning evacuees to shelters or assigning patients to hospitals during emergencies because CCNVD allots routes (e.g., evacuation routes) or limited resource (e.g., gas, water, or shelters) equally, efficiently, and more safely to evacuees (or other clients). One of the biggest challenges in this problem is to minimize the computational cost to construct a CCNVD in an emergency situation. The chapter provides three algorithms to efficiently construct a CCNVD.

KwangSoo Yang, Shashi Shekhar

Chapter 4. Distance-Constrained k Spatial Sub-networks

Abstract

In this chapter, we introduce a spatial network covering problem, namely Distance-Constrained k Spatial Sub-Networks (DCSSN). The main goal of the spatial network covering problem is to assign potential facilities to a finite set of demands that can maximize the total benefit under spatial constraints (e.g., distance, capacity, etc.). Given a graph and a set of spatial events, the goal of Distance-Constrained k Spatial Sub-Networks (DCSSN) problem is to find k sub-networks that meet a distance constraint and maximize the number of spatial events covered by the sub-networks. The DCSSN problem is important for many societal applications, such as police patrol assignment and emergency response assignment. The problem is NP-hard; it is computationally challenging because of the large size of the transportation network and the distance constraint. This chapter describes an algorithm that can create DCSSN.

KwangSoo Yang, Shashi Shekhar

Chapter 5. Evacuation Route Planning

Abstract

Evacuation route planning (ERP) is an important component of emergency management that seeks to minimize the loss of life or harm to the public during natural disasters or terrorist attacks. Given a transportation network, a population, and a set of destinations, the goal of the Evacuation Route Planning problem is to produce routes that minimize the evacuation time for the population. The problem is challenging because of the large size of network data, the large number of evacuees, and the need to account for capacity constraints in the road network. Efficient spatial network query processing mechanism are essential to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters. This chapter presents algorithms for ERP that explicitly exploit the spatial structure of road networks to minimize the computational time.

KwangSoo Yang, Shashi Shekhar

Chapter 6. Storage Schemes for Spatio-Temporal Network Datasets

Abstract

Emerging large-sized Spatial Network Big Data require novel data storage and access methods. Increasingly, these big data contain both spatial and temporal network data. Given a spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN operations. The SSTN problem is important for many societal applications, such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). This chapter describes storage methods that minimize disk I/O costs for two STN operations (i.e., LGetOneSuccessor() and LGetAllSuccessors()).

KwangSoo Yang, Shashi Shekhar

Chapter 7. Summary

Abstract

Spatio-temporal networks (STN) are today the very heart of our modern infrastructure. Ever increasing volumes of STN data collected from GPS systems, sensors on roadways and in vehicle engines, etc.

KwangSoo Yang, Shashi Shekhar

Titel: Spatial Network Big Databases
verfasst von: KwangSoo Yang
Shashi Shekhar
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-56657-3
Print ISBN: 978-3-319-56656-6
DOI: https://doi.org/10.1007/978-3-319-56657-3

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 1. Spatial Network Big Databases: An Introduction

Chapter 2. Basic Graph Algorithms

Chapter 3. Capacity Constrained Network Voronoi Diagrams

Chapter 4. Distance-Constrained k Spatial Sub-networks

Chapter 5. Evacuation Route Planning

Chapter 6. Storage Schemes for Spatio-Temporal Network Datasets

Chapter 7. Summary

Premium Partner