Collaborative Research: Large-Scale Analysis of Sensor-Based Geometric Data

Stanford University, Stanford CA

Investigators

Abstract

Geometric data derived from sensors is becoming ubiquitous, ranging from temperature and pressure data sampled over wide areas to continuous 3D scans of entire city streets. Although many more examples can be given, the above share the common characteristics that the relevant sensors are geographically dispersed and that the data itself is dynamically generated, often unstructured, highly variable, and possibly massive. The goal of this project is to investigate the intrinsic computational complexity and to develop fundamental algorithms for geometric problems involving such distributed networked spatiotemporal data. Potential applications include analyzing environmental data for ecological forecasting (e.g., predicting bio-diversity), landslide or debris flow prediction over extended areas, mining data on trajectories of vehicles or people for traffic management, detecting similar shapes across geographically separated regions for security or asset tracking, and many others. Traditional geometric algorithms assume that all data is centrally available and that random access to the data is efficient --- assumptions that are clearly violated in the distributed networked setting. A key component of the project is to develop geometric summaries that preserve the essential features and structure of the data and to study the fundamental trade-offs between the relevant parameters, including the size, accuracy, utility, stability, and computational complexity of these summaries. The project builds upon the existing sophisticated techniques such as epsilon-nets and approximations, coresets, discrepancy theory, range searching, persistent homology, surface reconstruction and simplification, kinetic data structures, and others. The research involves developing lightweight distributed and streaming algorithms as well as enhancing the theoretical underpinnings of large-scale sensor networks.