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

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

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.