CAREER: Data Structures and Streaming Algorithms

数据结构是计算机程序中的基本对象。它们是组织数据的复杂方法，以便用户可以有效地检索有关数据的某些信息。一些应用程序的数据随着时间的推移而逐渐演变，因此，数据结构也需要快速重组，以反映这些应用程序的数据更新。数据结构的一个显著类别是流式算法，其在使用非常小的存储器的同时以顺序次序处理输入数据。流算法维护一个数据结构，并在处理输入时不断更新它，而不必记住所有输入数据。这种情况发生在大量数据只是移动而没有被存储的任何地方，并且必须生成某些类型的摘要信息，例如，在互联网交换机。该项目旨在加深对高效数据结构和小空间流算法可以做什么和不能做什么的理解。该项目还为学生创造了在新的研究生课程和本科生研讨会上学习小空间算法的机会。该项目的重点是数据结构和流算法的内存消耗，运行时间和准确性之间的权衡。该项目从几个方向研究上下界问题，包括静态字典问题，动态数据结构的多项式下界，空间限制下的动态数据结构的更强下界，以及多遍流中的图问题，以及仅插入流的算法。在研究这些具体问题的同时，该项目更重要的目标是开发通用技术，以实现低成本和高精度的数据结构和技术，以推理其局限性。该奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。

Data structures are fundamental objects in computer programs. They are sophisticated ways of organizing data so that a user can efficiently retrieve certain information about the data. Some applications have data gradually evolving over time, hence, data structures also need to be quickly reorganizable to reflect the data updates for such applications. A notable class of data structures are streaming algorithms, which process input data in the sequential order while using very small memory. A streaming algorithm maintains a data structure and keeps updating it as the input is being processed, without having to remember all the input data. This situation occurs wherever large amounts of data just move through, without being stored, and certain types of summary information have to be generated, as, e.g., in internet switches. This project aims to deepen the understanding of what efficient data structures and small space streaming algorithms can and cannot do. The project also creates opportunities for students to learn about small-space algorithms in a new graduate course and undergraduate seminars.The focus of this project is the tradeoffs between memory consumption, running time and accuracy for data structures and streaming algorithms. This project studies both upper and lower bound questions in several directions, including the static dictionary problem, polynomial lower bounds for dynamic data structures, stronger lower bounds for dynamic data structures under space restrictions, as well as graph problems in multi-pass streaming, and algorithms for insertion-only streams. While studying these specific questions, the more essential objective of the project is to develop generic techniques for achieving low costs and high accuracy data structures and techniques for reasoning about their limitations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.