Approximation Algorithms for Data Streams

数据流计算正在成为大型网络环境中分析、监测和事件检测的重要模型之一，例如互联网、电话网络和用于观测科学的传感器网络。通常，数据流对大量数据集的计算进行建模。通常，数据的大小是如此之大，以至于它产生了过高的成本（在时间或基础设施上），无法允许有效的随机访问。因此，在数据流算法中，允许算法的空间明显小于输入的大小。在一些场景中，输入数据甚至没有存储在其他地方，只允许对数据进行一次传递。由于空间的限制，数据流计算通常无法寻求精确解，因此需要考虑近似算法来寻找近最优解。此外，数据流的应用，即监控和分析，通常更喜欢快速的接近最优解，而不是昂贵的多项式时间精确解。本提案的目标是为数据流中的几个关键问题设计近似算法。该提案还将尝试为流算法开发广泛的技术和框架。在进行理论研究的同时，我们还将探索与实践有关的问题。鉴于数据流与大型网络的相关性，提出的数据流算法研究将产生广泛的影响。

Data Stream computation is emerging as one of the important models for analysis, monitoring and event detection in context of large networks, e.g., the internet, telephone networks, and sensor networks for observational sciences. In general, data streams model computations over massive data sets. Often, the size of the data is so large that it incurs too high a cost (in time or infrastructure) to allow efficient random access.Thus in a data stream algorithm the space allowed to an algorithm is significantly smaller than the size of the input. In several scenarios, the input data is not even stored elsewhere, allowing only a single pass over the data.Due to the space bounds, data stream computation typically cannot seek exact solutions and therefore consider approximation algorithms to find near optimal solutions. Furthermore, the applications of data streams, i.e., monitoring and analysis, often prefer a fast near optimal solution compared to an expensive polynomial time exact solution.The goal of this proposal is to design approximation algorithms for several key problems in data streams. The proposal will also attempt to develop broad techniques and frameworks for stream algorithms. Along with our theoretical investigations, we will also explore problems related to practice. Given the relevance of the data streams to large networks the proposed algorithmic research in data streams will have a broadimpact.