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

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

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.