AF: Small: Collaborative Research: Dynamic data structures for vectors and graphs in sublinear memory

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

• 批准号: 1951384
• 负责人: Jelani Nelson
• 金额: $ 25万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1951384&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.

次线性空间数据结构最近引起了人们的广泛兴趣，其应用例如流算法、分布式计算、随机线性代数和压缩感知。小空间解决方案适合快速缓存，从而也提供时间加速，并且在分布式设置中需要更少的存储和带宽。该提案旨在开发新的方法来设计和分析两个看似不同但密切相关的对象的亚线性空间数据结构：向量和图。 PI 还计划教授高级研究生课程，其主题与该项目的重点重叠。此外，两位 PI 都计划培训和指导研究生和本科生进行研究、组织研讨会并撰写调查文章。 PI 还计划参加针对非计算机科学家和 K-12 学生的外展活动，并扩大对计算的参与。研究本身也可能具有工业影响，与数据库、网络流量分析和数据挖掘相关。PI 将重点关注旋转栅门流模型可以捕获的一组问题：R^ 中的一些高维向量 x n 接收坐标更新，在图的情况下可以有 n = (|V| 选择 2) （其中 V 是顶点集），然后边插入/删除对应于 x 中某些条目的加/减。该项目旨在进一步理解与向量更新的小空间动态数据结构相关的基本问题，特别是与图问题相关的问题。例如：* 小空间向量更新数据结构：仅插入情况：仅插入情况下，向量更新 x 的增量坐标，因此 x 是数据流中各种项出现次数的频率计数向量。 PI 计划解决该模型中的一些最基本的问题，例如范数估计、重大问题和统计数据的连续监控。*完全动态流和图形应用：许多最著名的小空间动态数据结构对于图问题，通过简化为向量更新问题来进行操作。例如，唯一已知的谱稀疏器的近线性空间算法通过减少到 l_2 重量级来进行操作，而连通性、k 边连通性、最小生成树和其他几个算法则减少到向量坐标采样问题。但许多未解决的问题仍然存在，例如动态流中连接的最佳空间复杂度是多少？ PI 还计划调查其他几个动态图和超图问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Fast optimal locally private mean estimation via random projections

通过随机投影快速最优局部私有均值估计

• 发表时间: 2023-12
• 期刊: Thirty-seventh Annual Conference on Neural Information Processing Systems (NeurIPS
• 作者: Asi, Hilal;Feldman, Vitaly;Nelson, Jelani;Nguyen, Huy;Talwar, Kunal
• 通讯作者: Talwar, Kunal

Private frequency estimation via projective geometry

通过射影几何进行私人频率估计

• 发表时间: 2022-01
• 期刊: Proceedings of the 39th International Conference on Machine Learning (ICML
• 作者: Feldman, Vitaly;Nelson, Jelani;Nguyen, Huy L.;Talwar, Kunal
• 通讯作者: Talwar, Kunal

Estimation of Entropy in Constant Space with Improved Sample Complexity

提高样本复杂度的恒定空间中的熵估计

• 发表时间: 2022-12
• 期刊: Proceedings of the 34th Annual Conference on Advances in Neural Information Processing Systems (NeurIPS
• 作者: Aliakbarpour, Maryam;McGregor, Andrew;Nelson, Jelani;Waingarten, Erik
• 通讯作者: Waingarten, Erik

Optimal Bounds for Approximate Counting

近似计数的最佳界限

• DOI: 10.1145/3517804.3526225
• 发表时间: 2022-06
• 期刊: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Nelson, Jelani;Yu, Huacheng
• 通讯作者: Yu, Huacheng

An Improved Sketching Algorithm for Edit Distance

一种改进的编辑距离草图算法

• 发表时间: 2021-01
• 期刊: STACS
• 作者: Jin, Ce;Nelson, Jelani;Wu, Kewen
• 通讯作者: Wu, Kewen