CAREER: New Methods for Central Streaming Problems

职业：解决中央流媒体问题的新方法

• 批准号: 2244899
• 负责人: Vladimir Braverman
• 金额: $ 50万
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2024-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2244899&HistoricalAwards=false
• 关键词: CAREER; New; Methods; Central; Streaming

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.

流媒体模型是一种强大的计算模型，在过去十年中对计算机科学产生了重大影响。最近的事态发展表明，在诸如网络，机器学习，天文学和统计推断等众多应用中流式传输方法的关键需求。该项目将开发新的流和素描算法，这些算法将适用于上述领域。该项目将支持本科研究，并吸引学生从事最先进的理论问题。该项目将通过与独立学校Local 1（IHS）合作（在巴尔的摩市的公立特许高中）合作来促进STEM教育，少数族裔学生约占学生团体的60％。该项目将有助于组织（i）为第一代学生组织研讨会，以及（ii）约翰·霍普金斯大学（Johns Hopkins University）的年度Sublinear算法研讨会。该项目将促进核心教育，并将引入新的高级课程和研讨会，这些课程和研讨会将向非理论学生传达算法原理。在1996年，Alon，Matias和Szegedy发表了一篇有关流算法的基本论文。本文在流模型中介绍了近似频率矩的问题，并提出了开放问题，？在流中可以近似哪些基于频率的功能？自1996年以来，对数据流的研究取得了巨大进展。尽管取得了这种进步，但我们对许多基本流媒体问题的理解远非完整。该项目的主要技术目标是开发新算法，这些算法将解决中心问题并克服现有的流媒体方法障碍。具体目标是以下内容：（1）回答Alon，Matias和Szegedy的主要开放问题，并为所有基于频率的功能获得一个零法律。 （2）发现滑动窗口模型与无界模型之间的关系。将此知识扩展到衰减和分布式模型。 （3）为数据流设计新的采样方法。将滑动窗口模型的采样方法扩展到衰减模型，改进加权和分布式采样。

项目成果

Universal Streaming of Subset Norms

子集规范的通用流式传输

• DOI: 10.4086/toc.2022.v018a020
• 发表时间: 2022
• 期刊: Theory of Computing
• 影响因子: 1
• 作者: Braverman, Vladimir;Krauthgamer, Robert;Yang, Lin F.
• 通讯作者: Yang, Lin F.

Sublinear time spectral density estimation

• DOI: 10.1145/3519935.3520009
• 发表时间: 2021-04
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: V. Braverman;A. Krishnan;Christopher Musco

Lower Bounds for Pseudo-Deterministic Counting in a Stream

流中伪确定性计数的下界

• 发表时间: 2023
• 期刊: Leibniz international proceedings in informatics
• 作者: Braverman, V.;Krauthgamer, R.;Krishnan, A.;Sapir, S.
• 通讯作者: Sapir, S.