CAREER: New Methods for Central Streaming Problems

流模型是一种强大的计算模型，在过去十年中对计算机科学产生了重大影响。最近的发展表明，在网络、机器学习、天文学和统计推断等众多应用中对流方法的迫切需求。该项目将开发适用于上述领域的新的流媒体和草图算法。该项目将支持本科生研究并让学生参与前沿理论问题的研究。该项目将通过与巴尔的摩市的一所公立特许高中 Independence School Local 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.