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; 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.

代表描述数据关系的最直观和自然方法之一的图是众多应用程序不可或缺的。它们在Web搜索，神经和社交网络分析以及代表复杂知识等领域中尤为重要。现代图的规模，再加上新的基于云的处理基础架构，已经揭示了开发更有效的方法来处理大图的方法。 该项目是由一个至关重要的问题驱动的：“哪些技术导致极其有效，可扩展的算法？” 研究目标是推动设计构成现代数据中心的大规模平行和分布式计算框架的高效大规模图算法的设计。 该项目包括一项教育计划，其中包括向高中生开放的年度编程竞赛，以及旨在培养算法设计思维方式并吸引多元化学生进入计算机科学的大学生。 比赛的要素还将为原则研究者的课程提供信息。该项目通过研究核心图理论问题（例如匹配，顶点涵盖和最密集的子绘图）来针对基本问题，以用于并行和分布式计算的大型现代框架。 该项目旨在通过开发新的“计算”技术中的新“稀疏”技术来生产创新的方法和更有效的算法来处理大量图形，其主要目的是通过考虑精心制作的输入图来执行计算任务。 该项目概述了两个主要推力，分别是（1）sublinear制度的计算中的稀疏，以及（2）线性制度计算中的稀疏。 该项目中应对的算法挑战将重点关注各种大规模制度，尤其是关于输入图的大小与可用计算单元的能力之间的关系。本奖奖反映了NSF的法定任务，并通过使用该基金会的智力优点和广泛的影响来评估CRITERIA CRITERIA CRITERIA。