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)线性区域计算的稀疏化。在这个项目中解决的算法挑战将集中在各种大规模的制度，特别是关于输入图的大小和可用计算单元的能力之间的关系。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。