CAREER: Data Structures and Streaming Algorithms

职业：数据结构和流算法

• 批准号: 2339942
• 负责人: Huacheng Yu
• 金额: $ 65万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-01 至 2029-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2339942&HistoricalAwards=false
• 关键词: CAREER; Data; Structures; Streaming; Algorithms

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.

数据结构是计算机程序中的基本对象。它们是组织数据的复杂方式，因此用户可以有效检索有关数据的某些信息。 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 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.该项目旨在加深对哪些有效的数据结构和小空间流算法可以做到也不能做的理解。 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.