CAREER: Sublinear Graph Algorithms: New Insights for Foundational Problems

职业：次线性图算法：基本问题的新见解

• 批准号: 1942010
• 负责人: Aaron Bernstein
• 金额: $ 55.18万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-01-15 至 2025-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942010&HistoricalAwards=false
• 关键词: CAREER; Sublinear; Graph; Algorithms; New

Graphs are one of the most natural ways to represent relationships between data and are used to model a wide variety of settings: social networks, the communication infrastructure, the interconnections of financial markets, metabolic processes, and the wiring of the human brain, to name a few. Processing such graphs has long been a cornerstone of computer science research, but the rise of big data poses unique computational challenges, as the scale of the graphs in these applications has far outpaced available computing power. The goal of this project is to develop a new toolkit for processing massive graphs. This project studies a novel set of research questions in the analysis of big data, and the new tools developed can be applied to foundational optimization problems such as shortest paths and matching that are central to applications in computer science, social networks, biology, and computational economics. The focus on foundational problems allows the project to bring together undergraduate and graduate students from a wide range of backgrounds. In additional to PhD mentoring and high-school outreach, the education plan includes research opportunities for undergraduates and the development of a new course in sublinear graph algorithms at Rutgers University.This project centers on three major challenges to processing massive graphs. The first is that such graphs are too large to fit in the memory of a computer, so the data must be compressed on the fly. The second is that it would take too long for a single computer to process the graph, so the computation is distributed over many machines. The third that is that in many applications the underlying graph is changing over time and it is necessary to respond to these changes locally. The project develops novel tools for tackling each individual challenge. At the same time, the project introduces general frameworks that connect the studies of these different challenges and lead to tools that can overcome a broad set of obstacles simultaneously. More specifically, what unifies the above challenges is the need to extrapolate global information about the entire graph from local information computed in small regions. For example, can one detect overloaded vertices from a small random sample of the graph? How can shortest paths in different regions be patched together to form a path from one end of the graph to another? How can a graph be compressed to only retain the most relevant edges? By answering these and related questions, the research will help extend the motivating applications to significantly larger scales and will lead to new mathematical insights into the structure of graphs.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.

图表是表示数据之间关系的最自然的方式之一，并用于对各种各样的设置进行建模：社交网络、通信基础设施、金融市场的互连、代谢过程和人脑的布线，仅举几例。处理此类图形长期以来一直是计算机科学研究的基石，但大数据的兴起带来了独特的计算挑战，因为这些应用中图形的规模远远超过了可用的计算能力。这个项目的目标是开发一个新的工具包来处理大量的图形。该项目研究了大数据分析中的一系列新的研究问题，开发的新工具可应用于计算机科学、社交网络、生物学和计算经济学应用的核心最短路径和匹配等基础优化问题。对基础问题的关注使该项目能够汇集来自广泛背景的本科生和研究生。除了博士生导师和高中外展，该教育计划还包括为本科生提供研究机会，并在罗格斯大学开发一门新的次线性图算法课程。该项目围绕处理海量图的三大挑战。首先，这样的图形太大，无法放入计算机的内存，因此数据必须在运行中压缩。第二个问题是，一台计算机处理图形需要太长的时间，因此计算分布在许多机器上。第三，在许多应用程序中，底层图形会随着时间的推移而变化，因此有必要在本地响应这些变化。该项目开发了新的工具来应对每一个挑战。与此同时，该项目引入了通用框架，将这些不同挑战的研究联系起来，并导致可以同时克服一系列障碍的工具。更具体地说，统一上述挑战的是需要从小区域中计算的局部信息推断有关整个图的全局信息。例如，可以从图的一个小的随机样本中检测过载的顶点吗？如何将不同区域中的最短路径拼接在一起，形成从图的一端到另一端的路径？如何压缩图以仅保留最相关的边？通过回答这些问题和相关问题，该研究将有助于将激励性应用扩展到更大的规模，并将导致对图形结构的新的数学见解。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

A framework for dynamic matching in weighted graphs

加权图中动态匹配的框架

• DOI: 10.1145/3406325.3451113
• 发表时间: 2021
• 期刊: Symposium on Theory of Computing
• 作者: Bernstein, Aaron;Dudeja, Aditi;Langley, Zachary
• 通讯作者: Langley, Zachary

Incremental SCC Maintenance in Sparse Graphs

稀疏图中的增量 SCC 维护

• DOI: 10.4230/lipics.esa.2021.14
• 发表时间: 2021
• 期刊: 29th Annual European Symposium on Algorithms (ESA 2021
• 作者: Bernstein, Aaron;Dudeja, Aditi;Pettie, Seth
• 通讯作者: Pettie, Seth

Decremental Matching in General Graphs

一般图中的递减匹配

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Assadi, Sepehr;Bernstein, Aaron;Dudeja, Aditi
• 通讯作者: Dudeja, Aditi

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary

• DOI: 10.4230/lipics.icalp.2022.20
• 发表时间: 2020-04
• 期刊: ArXiv
• 作者: A. Bernstein;Jan van den Brand;M. Gutenberg;Danupon Nanongkai;Thatchaphol Saranurak;Aaron Sidford;He Sun