CAREER: New Methods for Central Streaming Problems

流模型是一种强大的计算模型，在过去十年中对计算机科学产生了重大影响。最近的发展表明，在网络、机器学习、天文学和统计推断等众多应用中，对流方法的迫切需求。该项目将开发适用于上述领域的新的流媒体和素描算法。该项目将支持本科生的研究，并让学生参与前沿理论问题的研究。该项目将通过与巴尔的摩市公立特许高中独立学校当地1(IHS)合作来促进STEM教育，那里的少数族裔学生约占学生总数的60%。该项目将有助于在约翰霍普金斯大学举办(I)第一代学生讲习班和(Ii)一年一度的次线性算法讲习班。该项目将促进核心教育，并将引入新的高级课程和研讨会，向非理论专业的学生传达算法原理。1996年，Alon、Matias和Szegedy发表了一篇关于流算法的基础论文。本文介绍了流模型中频率矩的逼近问题，并提出了一个有待解决的问题：还有哪些基于频率的函数可以在流上逼近？自1996年以来，对数据流的研究取得了很大的进展。尽管取得了这一进展，但我们对许多基本的流媒体问题的理解还远远不完整。该项目的主要技术目标是开发新的算法，以解决中心问题并克服流方法的现有障碍。具体目标如下：(1)回答Alon，Matias和Szegedy提出的主要公开问题，得到所有基于频率的函数的零一定律。(2)揭示了滑动窗口模型与无界模型之间的关系。将这一知识扩展到衰变和分布模型。(3)设计了新的数据流采样方法。将滑动窗口模型的采样方法扩展到衰减模型，改进了加权采样和分布式采样。

The streaming model is a powerful model of computation that has made a significant impact on computer science over the past decade. Recent developments demonstrate the critical need for streaming methods in numerous applications such as networking, machine learning, astronomy and statistical inference. The project will develop new streaming and sketching algorithms that will be applicable in the aforementioned areas. The project will support undergraduate research and engage students in working on cutting-edge theoretical problems. The project will promote STEM education by collaborating with Independence School Local 1 (IHS), a public charter high school in Baltimore city, where minority students constitute about 60 percent of the student body. This project will help to organize (I) a workshop for first generation students and (II) an annual Sublinear Algorithms Workshop at Johns Hopkins University. The project will promote core education and will introduce new advanced courses and seminars that will convey the principles of algorithms to non-theory students.In 1996, Alon, Matias and Szegedy published a fundamental paper on streaming algorithms. The paper introduced the problem of approximating frequency moments in the streaming model and asked the open question, ?What other frequency-based functions can be approximated on streams?? Since 1996 the research on data streams has resulted in great progress. Despite this progress, our understanding of many fundamental streaming problems is far from being complete. The main technical objective of this project is to develop new algorithms that will resolve central problems and overcome existing barriers of streaming methods. The specific goals are the following: (1) Answer the main open question of Alon, Matias and Szegedy and obtain a zero-one law for all frequency-based functions. (2) Discover the relation between the sliding window model and the unbounded model. Extend this knowledge to the decay and distributed models. (3) Design new sampling methods for data streams. Extend the sampling methods for the sliding window model to decay models, improve the weighted and distributed sampling.