AF: Small: Collaborative Research: Dynamic Data Structures for Vectors and Graphs in Sublinear Memory
AF: Small: Collaborative Research: Dynamic Data Structures for Vectors and Graphs in Sublinear Memory
批准号:
1909314
负责人:
Huy Nguyen
金额:
$25.0万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2019
资助国家:
美国
项目状态:
已结题
起止时间:
2019-10-01 至 2022-09-30
中文摘要
次线性空间数据结构最近引起了人们的极大兴趣,例如在流算法、分布式计算、随机化线性代数和压缩传感中的应用。小空间解决方案适合快速缓存,因此也提供了时间加速,而且在分布式设置中还需要更少的存储和带宽。这项提议旨在开发新的方法来设计和分析两个看似不同但密切相关的对象的次线性空间数据结构:矢量和图形。PIS还计划教授高级研究生课程,这些课程的主题与本项目的重点重叠。此外,这两个私人投资机构都计划在研究方面培训和指导研究生和本科生,组织研讨会,并撰写调查文章。投资促进机构还计划参加面向非计算机科学家和K-12学生的外联活动,并扩大对计算机的参与。这项研究本身也可能产生工业影响,涉及数据库、网络流量分析和数据挖掘。PI将集中在旋转栅门流动模型可以捕获的一组问题上:R^n中的某个高维向量x接收坐标方向的更新,在图的情况下,其可能具有n=(|V|Choose 2)(其中V是顶点集),并且边插入/删除对应于x中的某个条目的加/减。本项目旨在进一步理解与用于向量更新的小空间动态数据结构相关的基本问题,尤其是当它们涉及图问题时。例如:*小空间向量更新数据结构:仅插入的情况:在仅插入的情况下,向量更新x的增量坐标,使得x是数据流中各种项的出现次数的频率计数向量。PI计划解决该模型中的一些最基本的问题,例如范数估计、重击和统计数据的连续监控。*完全动态的流和对图形的应用:许多最著名的小空间动态数据结构用于图形问题的操作归结为向量更新问题。例如,已知的唯一用于谱稀疏器的近线性空间算法是通过归结到L_2重击来实现的,而连通性、k边连通性、最小生成树等算法则归结为向量坐标采样问题。然而,仍然存在许多悬而未决的问题,例如,动态流中的连接的最佳空间复杂性是多少?PIS还计划调查其他几个动态图形和超图问题。这一裁决反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。
英文摘要
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.
期刊论文(4)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
DOI:
10.48550/arxiv.2203.00194
发表时间:
2022-03
期刊:
影响因子:
--
作者:
[V. Feldman;Jelani Nelson;Huy L. Nguyen;Kunal Talwar]
通讯作者:
V. Feldman;Jelani Nelson;Huy L. Nguyen;Kunal Talwar
DOI:
10.1609/aaai.v36i6.20565
发表时间:
2021-05
期刊:
影响因子:
--
作者:
[Anamay Chaturvedi;Matthew D. Jones;Huy L. Nguyen]
通讯作者:
Anamay Chaturvedi;Matthew D. Jones;Huy L. Nguyen
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
具有基数约束的子模最大化的最优流算法
DOI:
10.4230/lipics.icalp.2020.6
发表时间:
2020
期刊:
and Programming
影响因子:
--
作者:
[Alaluf, Naor, Ene, Alina, Feldman, Moran, Nguyen, Huy L, Suh, Andrew]
通讯作者:
Suh, Andrew
Projection-Free Bandit Optimization with Privacy Guarantees
具有隐私保证的无投影强盗优化
DOI:
--
发表时间:
2021
期刊:
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子:
--
作者:
[Ene, Alina, Nguyen, Huy L, Vladu, Adrian]
通讯作者:
Vladu, Adrian
Collaborative Research: AF: Medium: Sketching for privacy and privacy for sketching
-
批准号:2311649
-
项目类别:Continuing Grant
-
资助金额:$60.0万
-
财政年份:2023
-
负责人:Huy Nguyen
-
依托单位:
Regularity and Stability Analysis of Free-Boundary Problems in Fluid Dynamics
-
批准号:2205710
-
项目类别:Standard Grant
-
资助金额:$34.0万
-
财政年份:2022
-
负责人:Huy Nguyen
-
依托单位:
Analysis of Incompressible Flows with Rigid and Free Boundaries
-
批准号:2205734
-
项目类别:Continuing Grant
-
资助金额:$17.37万
-
财政年份:2021
-
负责人:Huy Nguyen
-
依托单位:
Analysis of Incompressible Flows with Rigid and Free Boundaries
-
批准号:1907776
-
项目类别:Continuing Grant
-
资助金额:$17.37万
-
财政年份:2019
-
负责人:Huy Nguyen
-
依托单位:
CAREER: Faster and Smaller Sketches for Bigger Data
-
批准号:1750716
-
项目类别:Continuing Grant
-
资助金额:$49.99万
-
财政年份:2018
-
负责人:Huy Nguyen
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: