CAREER: Fast Scalable Graph Algorithms

职业：快速可扩展图算法

• 批准号: 2340048
• 负责人: Slobodan Mitrovic
• 金额: $ 62.33万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2029-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2340048&HistoricalAwards=false
• 关键词: CAREER; Fast; Scalable; Graph; Algorithms

Graphs, representing one of the most intuitive and natural methods for depicting data relationships, are integral to numerous applications. They are particularly crucial in domains like Web search, neural and social network analysis, and in representing complex knowledge. The scale of modern graphs, coupled with new cloud-based processing infrastructure, has exposed a need to develop more efficient methods to process large graphs. This project is driven by a crucial question: "What techniques lead to extremely efficient, scalable algorithms?" The research objective is to advance the design of efficient, large-scale graph algorithms for the massively parallel and distributed computational frameworks that comprise modern data centers. The project includes an educational plan that includes an annual programming competition open to high school students, as well as undergraduates aimed at fostering an algorithm-design mindset and at attracting diverse students into computer science. Elements of the contest will also inform the principle investigator's courses.The project targets fundamental questions by studying core graph theory problems -- such as matchings, vertex covers, and densest subgraphs -- in the context of large-scale modern frameworks for parallel and distributed computation. This project aims to produce innovative methods and more efficient algorithms for processing massive graphs by developing new "sparsification in computation" techniques whose main aim is to perform a computational task by considering carefully crafted subsets of the input graph. The project outlines two main thrusts, namely (1) sparsification in computation for the sublinear regime, and (2) sparsification in computation for the linear regime. The algorithmic challenges tackled in this project will focus on various large-scale regimes, particularly concerning the relationship between the sizes of input graphs and the capacities of the available computing units.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.

图形是描述数据关系的最直观和最自然的方法之一，是许多应用程序的组成部分。它们在网络搜索、神经和社交网络分析以及表示复杂知识等领域中尤为重要。现代图形的规模，加上新的基于云的处理基础设施，已经暴露出需要开发更有效的方法来处理大型图形。 这个项目是由一个关键的问题驱动的：“什么技术导致极其高效，可扩展的算法？”“研究目标是为构成现代数据中心的大规模并行和分布式计算框架推进高效的大规模图算法的设计。 该项目包括一个教育计划，其中包括每年一次的编程竞赛，向高中生和本科生开放，旨在培养算法设计思维，吸引不同的学生进入计算机科学。 该项目的目标是在大规模现代并行和分布式计算框架的背景下，通过研究核心图论问题（如匹配、顶点覆盖和可扩展子图）来解决基础问题。 该项目旨在通过开发新的“计算稀疏化”技术来产生用于处理大量图形的创新方法和更有效的算法，该技术的主要目的是通过考虑精心制作的输入图形子集来执行计算任务。 该项目概述了两个主要目标，即（1）次线性区域的计算稀疏化，以及（2）线性区域的计算稀疏化。 在这个项目中解决的算法挑战将集中在各种大规模的制度，特别是关于输入图形的大小和可用的计算单元的能力之间的关系。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。