CAREER: Data Structures and Streaming Algorithms

Princeton University, Princeton NJ

Investigators

Abstract

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.