CAREER: New Methods for Central Streaming Problems

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

• 批准号: 1652257
• 负责人: Vladimir Braverman
• 金额: $ 50万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-02-01 至 2022-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1652257&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.

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

项目成果

Streaming symmetric norms via measure concentration

• DOI: 10.1145/3055399.3055424
• 发表时间: 2015-11
• 期刊: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Jarosław Błasiok;Vladimir Braverman;Stephen R. Chestnut;Robert Krauthgamer;Lin F. Yang

Coresets for Clustering in Excluded-minor Graphs and Beyond

• DOI: 10.1137/1.9781611976465.159
• 发表时间: 2020-04
• 作者: V. Braverman;S. Jiang;Robert Krauthgamer;Xuan Wu

On the Noisy Gradient Descent that Generalizes as SGD

关于推广为 SGD 的噪声梯度下降

• 发表时间: 2020
• 期刊: Proceedings of Machine Learning Research
• 作者: Wu, Jingfeng;Hu, Wenqing;Xiong, Haoyi;Huan, Jun;Braverman, Vladimir;Zhu, Zhanxing
• 通讯作者: Zhu, Zhanxing

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order

• 发表时间: 2016-09
• 作者: V. Braverman;Stephen R. Chestnut;Robert Krauthgamer;Yi Li;David P. Woodruff;Lin F. Yang

Sketch and Scale Geo-distributed tSNE and UMAP

• DOI: 10.1109/bigdata50022.2020.9377843
• 发表时间: 2020-11
• 期刊: 2020 IEEE International Conference on Big Data (Big Data)
• 作者: Viska Wei;Nikita Ivkin;V. Braverman;A. Szalay