Geometric Computing over Distributed and Streaming Data

计算几何算法传统上是为集中式数据设置而设计的，其中数据在本地以持久形式可供算法使用。然而，越来越多的新兴应用程序不再适合这种传统的数据模型。例如，在传感器网络和位置感知移动计算中，数据是地理分布的，在大容量数据监控中，如分析互联网流量或网络点击，数据必须作为流处理，而不是存储。在这些技术趋势的推动下，研究人员开发了用于几何计算的分布式算法。为分布式或流数据设计数学基础的几何算法是具有挑战性的，因为算法必须在有限的计算资源下运行。特别是，传感器网络中的节点的电池功率、内存和带宽非常有限，因此从网络收集数据需要节点构建其空间测量的近似值。同样，数据流算法必须在单遍中处理数据，并计算总结数据重要特征的概要数据结构。这项研究开发了新的几何算法和数据结构，以优雅的方式处理资源(带宽、内存、功率)不足的问题，从而使解的质量与可用的资源相适应-资源越好，解的质量越高。特别是，研究提出了这样的资源自适应方法来发现传感器网络中的epsilon割，计算传感器观测的有限内存近似，发现多维数据流中的分层重击发者，以及几何数据流的保形聚类方法。许多对国家具有重大意义的挑战涉及到保护我们的物理和网络基础设施。能够使用灵活、资源自适应和可编程的软件工具远程监控这些系统并分析其数据至关重要。由于这些系统中的许多都处理分布式或流数据，因此本研究与这些应用程序具有直接的相关性。

Computational geometry algorithms traditionally have been designed for centralized data settings, where the data are available to algorithms locally and in a persistent form. Yet, a growing number of emerging applications no longer fit such a conventional data model. For instance, in sensor networks and location-aware mobile computing, data is geographically distributed, and in high-volume data monitoring, such as analysis of Internet traffic or web clicks, data must be processed as a stream, without being stored. Motivated by these technological trends, the investigator develops distributed algorithms for geometric computing.Designing mathematically grounded geometric algorithms for distributed or streaming data is challenging because the algorithms must operate with limited computational resources. In particular, nodes in a sensor network have very limited battery power, memory, and bandwidth, and so collecting data from the network requires nodes to construct approximations of their spatial measurements. Similarly, data stream algorithms must process the data in a single pass and compute synopsis data structures that summarize important features of the data. This research develops novel geometric algorithms and data structures that deal with insufficient resources (bandwidth, memory, power) in a graceful manner, so that the solution quality adapts to the resources available --- the better the resources, higher the solution quality. In particular, the research proposes such resource-adaptive methods to discover epsilon-cuts in sensor networks, compute bounded-memory approximations of sensor observations, discover hierarchical heavy hitters in multi-dimensional data streams, and shape-preserving clustering methods for geometric streams. Many challenges of national importance concern the protection of our physical as well as cyber infrastructures. Being able to monitor these systems remotely and analyze their data with flexible, resource-adaptive, and programmable software tools is critically important. Because many of these systems deal with distributed or streaming data, this research has direct relevance to those applications.