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

从传感器获得的几何数据正变得无处不在，从大范围采样的温度和压力数据到对整个城市街道的连续3D扫描。虽然可以给出更多的例子，但上面的共同特征是，相关传感器在地理上是分散的，并且数据本身是动态生成的，通常是非结构化的，高度可变，并且可能是海量的。这个项目的目标是研究内在的计算复杂性，并开发涉及此类分布式网络时空数据的几何问题的基本算法。潜在的应用包括分析环境数据以进行生态预测(例如，预测生物多样性)、扩展区域的滑坡或泥石流预测、挖掘车辆或人的轨迹数据以进行交通管理、在地理上分离的区域中检测相似形状以进行安全或资产跟踪，以及许多其他应用。传统的几何算法假设所有数据都集中可用，并且随机访问数据是有效的-在分布式网络环境中显然违反了这一假设。该项目的一个关键组成部分是制定几何摘要，以保留数据的基本特征和结构，并研究相关参数之间的基本权衡，包括这些摘要的大小、准确性、实用性、稳定性和计算复杂性。该项目建立在现有复杂技术的基础上，如epsilon网和近似、核集、差异理论、范围搜索、持久同调、表面重建和简化、动力学数据结构等。这项研究涉及开发轻量级分布式和流传输算法，以及增强大规模传感器网络的理论基础。

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.