AF: Small: Collaborative Research: Dynamic Data Structures for Vectors and Graphs in Sublinear Memory

AF：小：协作研究：子线性存储器中向量和图的动态数据结构

• 批准号: 1909314
• 负责人: Huy Nguyen
• 金额: $ 25万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909314&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Dynamic

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.

sublinear空间数据结构一直具有最近的兴趣，例如在流算法，分布式计算，随机线性代数和压缩传感中应用。小空间解决方案适合快速缓存，从而提供时间加速，并且还需要更少的存储空间，并且在分布式设置中需要更少的带宽。该建议旨在开发用于设计和分析两个看似不同但密切相关的对象的新方法：向量和图形。 PIS还计划教授高级研究生课程，其主题与该项目的重点重叠。此外，PIS都计划培训和指导研究生和本科生的学生研究，组织研讨会和撰写调查文章。 PIS计划还计划向非计算机科学家和K-12学生参加外展活动，并扩大参与计算的参与。 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 x中某些条目的加法/减法。该项目的目的是进一步了解与矢量更新相关的基本问题，尤其是与图形问题相关的小空间数据结构。 PI计划攻击该模型中一些最根本的问题，例如规范估计，重型击球手以及对统计数据的持续监视。例如，光谱稀疏器的唯一已知的几乎线性空间算法是通过还原为L_2重型击球手来运行的，以及用于连接性，K边缘连接性，最小跨越树的算法以及其他几个减少到矢量坐标坐标采样问题。尽管仍然存在许多开放问题，例如动态流中连通性的最佳空间复杂性是什么？ PIS还计划调查其他几个动态图和超图形问题。该奖项反映了NSF的法定任务，并认为使用基金会的知识分子优点和更广泛的影响审查标准，被认为值得通过评估。

项目成果

Private Frequency Estimation via Projective Geometry

• DOI: 10.48550/arxiv.2203.00194
• 发表时间: 2022-03
• 作者: V. Feldman;Jelani Nelson;Huy L. Nguyen;Kunal Talwar

Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

• DOI: 10.1609/aaai.v36i6.20565
• 发表时间: 2021-05
• 作者: 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

具有隐私保证的无投影强盗优化

• 发表时间: 2021
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Ene, Alina;Nguyen, Huy L;Vladu, Adrian
• 通讯作者: Vladu, Adrian