DC: Small: Data Streaming through a Complexity-Theoretic Lens

现代高度数字化的世界充满了人类活动，这些活动在连续不断的基础上产生了大量的数据流。 通过适当地分析、挖掘和监测这些数据流中的丰富信息，可以获得知识。然而，由于所涉及的数据规模庞大，传统的算法思维是不够的，人们需要数据流算法，可以在一个或几个扫描通道中有效地处理输入的内存，理想情况下与数据生成同步操作。数据流算法的领域，虽然可以追溯到1980年左右，但直到最近十年左右才真正活跃起来，已经开发了大量的算法，例如，各种统计分析、几何问题和图论问题。一个充满算法思想的领域应该得到坚实的理论基础。因此，本项目将调查这一领域的一些基本问题，重点是在这一重要的计算模型中可以实现和不可以实现的划分。通过研究基础问题，而不是过于关注特定的应用程序，该项目的方法将是算法和复杂性理论。该项目的一些代表性研究目标如下。 (1)完善我们对各种统计测量的空间复杂性的理解，特别是在多通道设置中。 (2)理解顺序相关流问题中随机性的力量。 (3)在基本流模型的更强变体（扩展）中证明下界。 (4)解决通信复杂性中的基本问题，这些问题是目前数据流复杂性中公开问题的核心，项目过程中取得的成果将在各机构的国际会议、讲习班和研讨会上传播。 该项目的教育部分将包括开发关于数据流算法的研究生课程，涵盖该领域的基础知识，并导致最近最重要的发现。

The modern, highly digitized world is replete with human activities that generate copious streams of data on a seemingly-continuous basis. There is knowledge to be gained by suitably analyzing, mining and monitoring the wealth of information in these data streams. However, due to the sheer scale of the data involved, traditional algorithmic thinking is inadequate and one needs data streaming algorithms that can process inputs memory-efficiently in one, or a few, scanning passes, ideally operating in sync with data generation.The area of data streaming algorithms, though dating back to about 1980, has truly come alive only in the last decade or so, with a wealth of algorithms having been developed for, e.g., various statistical analyses, geometric problems and graph-theoretic problems. An area rich with algorithmic ideas deserves sound theoretical underpinnings. Accordingly, this project shall investigate a number of fundamental questions in this area, focusing on the delineation of what can and cannot be achieved in this important computational model. By investigating foundational questions, rather than focusing too much on particular applications, the project's approach shall be that of algorithms-and-complexity theory.Some representative research goals of this project are as follows. (1) Refining our understanding of the space complexity of various statistical measures, especially in the multi-pass setting. (2) Understanding the power of randomness in order-dependent streaming problems. (3) Proving lower bounds in stronger variants (extensions) of the basic stream model. (4) Attacking fundamental questions in communication complexity that lie at the heart of current open questions in data stream complexity.Results obtained in the course of the project will be disseminated at international conferences, workshops and seminars at various institutions. The project's educational component shall consist of the development of a graduate-level course on data stream algorithms, covering the basics of the field and leading up to the most significant recent discoveries.