CAREER: New Methods for Central Streaming Problems

点击翻译按钮获取中文摘要

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.