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.