AF: Small: Collaborative Research: Dynamic data structures for vectors and graphs in sublinear memory
AF:小:协作研究:亚线性存储器中向量和图形的动态数据结构
基本信息
- 批准号:1951384
- 负责人:
- 金额:$ 25万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-07-01 至 2023-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Sublinear-space data structures have been of major recent interest, with applications for example in streaming algorithms, distributed computation, randomized linear algebra, and compressed sensing. Small-space solutions fit in fast cache, thus providing time speedups as well, and also require less storage and less bandwidth in distributed settings. This proposal aims to develop novel methods for designing and analyzing sublinear-space data structures for two seemingly different but closely related objects: vectors and graphs. The PIs also plan to teach advanced graduate courses whose topics overlap with the focus of this project. Furthermore, both PIs plan to train and mentor graduate and undergraduate students students in research, organize workshops, and write survey articles. The PIs plan to also participate in outreach activities to non-computer scientists and to K-12 students, and to broaden participation in computing. The research itself may also have industrial impact, being related to databases, network traffic analysis, and data mining.The PIs will focus on a set of problems that can be captured by the turnstile streaming model: some high-dimensional vector x in R^n receives coordinate-wise updates, which in the case of graphs could have n = (|V| choose 2) (where V is the set of vertices), and edge insert/deletion then corresponds to addition/subtraction from some entry in x. This project aims to further the understanding of fundamental questions related to small-space dynamic data structures for vector updates, and especially as they relate to graph problems.For example:* Small-space vector update data structures: the insertion-only case: In the insertion-only case, vector updates increment coordinates of x, so that x is a frequency-count vector of the number of occurrences of various items in a data stream. The PIs plan to attack some of the most fundamental problems in this model, such as norm estimation, heavy hitters, and continuous monitoring of statistics.* Fully dynamic streams and applications to graphs: Many of the best-known small-space dynamic data structures for graph problems operate by reducing to vector-update problems. For example, the only known nearly linear-space algorithm for spectral sparsifiers operates by reduction to l_2 heavy hitters, and algorithms for connectivity, k-edge connectivity, minimum spanning trees, and several others reduce to vector coordinate-sampling problems. Many open problems though still remain, e.g. what is the optimal space complexity for connectivity in dynamic streams? The PIs also plan to investigate several other dynamic graph and hypergraph problems.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.
亚线性空间数据结构最近引起了人们的极大兴趣,应用于流算法、分布式计算、随机线性代数和压缩感知等领域。小空间解决方案适合快速缓存,因此也提供了时间加速,并且在分布式设置中需要更少的存储和更少的带宽。本提案旨在为两个看似不同但密切相关的对象:向量和图,开发设计和分析亚线性空间数据结构的新方法。pi还计划教授高级研究生课程,其主题与该项目的重点重叠。此外,两个pi计划培训和指导研究生和本科生的研究,组织研讨会,并撰写调查文章。pi还计划参加面向非计算机科学家和K-12学生的外展活动,并扩大对计算机的参与。研究本身也可能有工业影响,涉及到数据库、网络流量分析和数据挖掘。pi将专注于一系列问题,这些问题可以由旋转门流模型捕获:R^n中的一些高维向量x接收坐标更新,在图的情况下可能有n = (|V|选择2)(其中V是顶点集),然后边缘插入/删除对应于x中的某些条目的加法/减法。该项目旨在进一步理解与矢量更新的小空间动态数据结构相关的基本问题,特别是与图问题相关的问题。*小空间向量更新数据结构:只插入的情况:在只插入的情况下,向量更新x的增量坐标,因此x是数据流中各种项出现次数的频率计数向量。pi计划解决该模型中的一些最基本的问题,例如规范估计、重磅打击和统计数据的持续监控。*全动态流和图的应用:许多著名的图问题的小空间动态数据结构通过简化为矢量更新问题来操作。例如,唯一已知的谱稀疏器的近线性空间算法是通过约简到l_2个重打击来操作的,而连通性、k边连通性、最小生成树和其他一些算法则归结为向量坐标采样问题。许多悬而未决的问题仍然存在,例如,动态流中连接的最佳空间复杂度是多少?pi还计划研究其他几个动态图和超图问题。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(5)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Fast optimal locally private mean estimation via random projections
通过随机投影快速最优局部私有均值估计
- DOI:
- 发表时间:2023
- 期刊:
- 影响因子:0
- 作者:Asi, Hilal;Feldman, Vitaly;Nelson, Jelani;Nguyen, Huy;Talwar, Kunal
- 通讯作者:Talwar, Kunal
Private Frequency Estimation via Projective Geometry
- DOI:10.48550/arxiv.2203.00194
- 发表时间:2022-03
- 期刊:
- 影响因子:0
- 作者:V. Feldman;Jelani Nelson;Huy L. Nguyen;Kunal Talwar
- 通讯作者:V. Feldman;Jelani Nelson;Huy L. Nguyen;Kunal Talwar
Estimation of Entropy in Constant Space with Improved Sample Complexity
提高样本复杂度的恒定空间中的熵估计
- DOI:
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Aliakbarpour, Maryam;McGregor, Andrew;Nelson, Jelani;Waingarten Erik
- 通讯作者:Waingarten Erik
Optimal Bounds for Approximate Counting
近似计数的最佳界限
- DOI:10.1145/3517804.3526225
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Nelson, Jelani;Yu, Huacheng
- 通讯作者:Yu, Huacheng
An Improved Sketching Algorithm for Edit Distance
一种改进的编辑距离草图算法
- DOI:
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Jin, Ce;Nelson, Jelani;Wu, Kewen
- 通讯作者:Wu, Kewen
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Jelani Nelson其他文献
Sketching and streaming high-dimensional vectors
绘制和流式传输高维向量
- DOI:
- 发表时间:
2011 - 期刊:
- 影响因子:0
- 作者:
Jelani Nelson - 通讯作者:
Jelani Nelson
Terminal Embeddings in Sublinear Time
亚线性时间的终端嵌入
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Yeshwanth Cherapanamjeri;Jelani Nelson - 通讯作者:
Jelani Nelson
Lower Bounds for Oblivious Subspace Embeddings
不经意子空间嵌入的下界
- DOI:
- 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
Jelani Nelson;Huy L. Nguyen - 通讯作者:
Huy L. Nguyen
Jelani Nelson的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Jelani Nelson', 18)}}的其他基金
Collaborative Research: AF: Medium: Sketching for privacy and privacy for sketching
合作研究:AF:中:为隐私而素描和为素描而隐私
- 批准号:
2311648 - 财政年份:2023
- 资助金额:
$ 25万 - 项目类别:
Continuing Grant
AF: Small: Collaborative Research: Dynamic data structures for vectors and graphs in sublinear memory
AF:小:协作研究:亚线性存储器中向量和图形的动态数据结构
- 批准号:
1908821 - 财政年份:2019
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
AF:Chaining methods and their applications to computer science
AF:链接方法及其在计算机科学中的应用
- 批准号:
1618373 - 财政年份:2016
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
CAREER: Sketching Algorithms for Massive Data
职业:海量数据的草图算法
- 批准号:
1350670 - 财政年份:2014
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
BIGDATA: F: DKA: Randomized methods for high-dimensional data analysis
BIGDATA:F:DKA:高维数据分析的随机方法
- 批准号:
1447471 - 财政年份:2014
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331401 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Real Solutions of Polynomial Systems
合作研究:AF:小:多项式系统的实数解
- 批准号:
2331400 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402572 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342245 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402571 - 财政年份:2024
- 资助金额:
$ 25万 - 项目类别:
Standard Grant