Research Area 5.1 Computational Architectures and Visualization: Geometric Graphs for Modeling and Analyzing Big Spatial Data
Abstract
Big spatial data sets are being collected and regularly updated by federal, state, and local government agencies, as well as by private companies, at an unprecedented rate, and the demand for these data sets is increasing. The tremendous opportunities provided by such high-resolution spatial data will depend on the ability of users to analyze and extract information from these data sets on a wide range of computational platforms. The task of analyzing modern data sets presents considerable algorithmic challenges given the volume, variety, velocity, and veracity of data. The spatial data are also invariably full of noise, inaccuracies, and outliers, and are often incomplete and approximate. This project will develop fast, scalable algorithms for constructing sparse geometric graphs (i.e., vertices are points in some geometric space, and edges are line segments connecting their endpoints) from big spatial data sets, which will act as small-size descriptors of the underlying space, so that various geometric/topological analyses on such data can be performed accurately as well as efficiently. The graphs constructed by these algorithms will be tailored to the analysis that needs to be performed. Algorithms will be developed for updating these graphs dynamically and for handling uncertainty in the data. I/O-efficient and parallel algorithms for constructing these graphs will be explored to cope with the big size of the data. Another key aspect of the proposed research will be to analyze not a single data set in isolation but rather the inter-relation and correspondences between different data sets. Therefore algorithms will be developed for computing maps between two geometric graphs. These maps will be used to: detect changes in data over time, identify common substructures over multiple data sets, transport information from one space to another, compare the results obtained by different methods, and integrate analysis on multiple data sets. The project has the potential to make a long-lasting impact in many areas. Several federal agencies and private companies are making significant investments in spatial data collection programs to support their key missions, and the ability to extract meaningful information from these big data sets will become increasingly important to their missions. The proposed research will be beneficial to a wide array of applications, including hydrology (e.g. flood-risk) analysis, path planning, resource allocation, facility monitoring and surveillance, and tools for military analysis and deployment. Technology developed under this project will be transferred through software development; presentation at workshops and conferences; and active collaboration with researchers and practitioners in other disciplines, in industry, and in army research labs.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1510408
Entities
People
- Pankaj Agarwal
Organizations
- Army Contracting Command
- Duke University
- United States Army