CAREER: Algorithmic Challenges and Opportunities in Spatial Data Analysis

North Carolina State University, Raleigh NC

Investigators

Abstract

Spatial data takes many forms including configuration spaces of robots or proteins, collections of shapes or measures, and physical models and measurements from new sensing technologies. These data sets often contain intrinsic, nonlinear, low-dimensional structure hidden in complex high-dimensional input representations. To uncover such structure one needs to adapt to local changes in scale, recognize multiscale structure, represent the intrinsic space underlying the data, compute with coarse approximate distances, and integrate heterogeneous data into meaningful distance functions. There is a need for algorithms and data structures that can search, represent, and summarize such data sets efficiently. The PI will develop new data structures, models of computation, sampling theories, sampling algorithms, and metrics for addressing these challenges. The specific aim of the project is to adapt hierarchical metric data structures to work with locally adaptive distances using new models of computation that only use approximate distance comparisons. These models acknowledge the reality that with sufficiently complex data, even a single distance computation can be expensive. A second specific aim is to develop new multiscale sampling theories as well as new algorithms for computing such samples. These samples and sampling algorithms will be applicable to a wide range of problems and will extend and generalize greedy and farthest-point strategies. A third specific aim is to develop algorithms for new metrics and distance functions for heterogeneous data to more accurately represent intrinsic structure in data. These algorithms will generalize methods used in both Voronoi refinement mesh generation and topological data analysis. The project will make geometric methods applicable to a much wider range of problems and with that comes the need for wider understanding of advanced geometry and topology. The PI will integrate research and education, introducing computer science students at both the undergraduate and graduate level to foundational ideas in spatial data analysis, from geometry to topology. The PI will also work one-on-one to mentor undergraduates from traditionally underrepresented groups and help train high school teachers.