CAREER: Data Structures and Streaming Algorithms
CAREER: Data Structures and Streaming Algorithms
批准号:
2339942
负责人:
Huacheng Yu
金额:
$65.0万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2024
资助国家:
美国
项目状态:
未结题
起止时间:
2024-03-01 至 2029-02-28
中文摘要
点击翻译按钮获取中文摘要
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
国内基金
海外基金
登录
查看更多内容
Scalable Learning and Optimization: High-dimensional Models and Online Decision-Making Strategies for Big Data Analysis
-
批准号:--
-
项目类别:合作创新研究团队
-
资助金额:--
-
批准年份:2024
-
负责人:姚韬
-
依托单位:
Data-driven Recommendation System Construction of an Online Medical Platform Based on the Fusion of Information
-
批准号:--
-
项目类别:外国青年学者研究基金项目
-
资助金额:--
-
批准年份:2024
-
负责人:江洋子
-
依托单位:
Development of a Linear Stochastic Model for Wind Field Reconstruction from Limited Measurement Data
-
批准号:--
-
项目类别:--
-
资助金额:40万元
-
批准年份:2020
-
负责人:Vikrant Gupta
-
依托单位:
基于Linked Open Data的Web服务语义互操作关键技术
-
批准号:61373035
-
项目类别:面上项目
-
资助金额:77.0万元
-
批准年份:2013
-
负责人:冯志勇
-
依托单位:
Molecular Interaction Reconstruction of Rheumatoid Arthritis Therapies Using Clinical Data
-
批准号:31070748
-
项目类别:面上项目
-
资助金额:34.0万元
-
批准年份:2010
-
负责人:Christine Nardini
-
依托单位:
高维数据的函数型数据(functional data)分析方法
-
批准号:11001084
-
项目类别:青年科学基金项目
-
资助金额:16.0万元
-
批准年份:2010
-
负责人:周迎春
-
依托单位:
染色体复制负调控因子datA在细胞周期中的作用
-
批准号:31060015
-
项目类别:地区科学基金项目
-
资助金额:25.0万元
-
批准年份:2010
-
负责人:莫日根
-
依托单位:
Computational Methods for Analyzing Toponome Data
-
批准号:60601030
-
项目类别:青年科学基金项目
-
资助金额:17.0万元
-
批准年份:2006
-
负责人:Axel Mosig
-
依托单位: