Geometric Computing over Distributed and Streaming Data

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

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.