CAREER: Parallel Algorithms and Frameworks for Graph and Hypergraph Processing

图表是一种用于对各种实体之间的交互进行建模的工具。大型图的高效处理因其在生物、化学、社会网络分析等领域的应用而备受关注。随着数据量的爆炸性增长，图变得非常大，可以包含数千亿个顶点和数万亿条边。各种应用程序还受益于将底层数据建模为超图，这使多个实体之间的关系能够比图形更好地表示。此外，这些数据集中的许多都是实时快速变化的，应用程序需要最新数据的计算结果。设计高性能的并行算法，以便能够及时地对图和超图进行分析是至关重要的。然而，编写高效的并行代码是出了名的困难。此外，目前在实践中使用的许多并行算法没有强有力的理论保证，导致它们在某些输入上执行得非常差。为了应对这些挑战，该项目涉及创建具有高度优化的后端的高级编程框架，以使非专家更容易为处理静态和流数据的图形和超图编写高性能并行程序。该项目还涉及设计在理论和实践中都很有效的并行算法，以便它们在所有可能的输入和许多机器参数下都能很好地执行，并优雅地扩展到更大的数据集。通过使用生成的算法和框架，科学家将能够使用高级工具在理论和实践上比以前更有效地执行海量输入的图和超图分析。该项目涉及为许多基本的图和超图问题设计新的并行基元和算法，在理论和实践上都是快速和高效的。新算法正在使用大规模多核机器在最大的公开可用的数据集上进行评估。该项目还涉及创建高级抽象和编程框架，以支持在静态和流数据上实现理论上有效的算法。首先，将设计一种用于图计算的领域特定语言，它将从算法和优化的高级规范中生成高效和高度优化的代码。其次，将开发一个统一的流图分析框架，该框架可以有效地支持对图的并行更新(同时运行算法和更新)、增量算法和时态分析。最后，将设计一种新的超图处理抽象和框架，它将支持理论上高效的超图算法的实现。这一结果将导致并行算法设计以及图形和超图分析编程框架的根本性进步。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs are a tool used to model the interactions between various entities. Efficiently processing large graphs has attracted significant attention due to its applications in various domains, such as biology, chemistry, and social network analysis. With the explosion in the volume of data, graphs have become very large and can contain hundreds of billions of vertices and trillions of edges. Various applications also benefit from modeling the underlying data as a hypergraph, which enables relationships among multiple entities to be represented better than a graph. In addition, many of these data sets are changing rapidly in real-time and applications require computing results on the latest data. It is crucial to design high-performance parallel algorithms to enable analysis to be done on graphs and hypergraphs in a timely fashion. However, writing efficient parallel code is notoriously difficult. Furthermore, many parallel algorithms used in practice today do not have strong theoretical guarantees, causing them to perform extremely poorly on certain inputs. To address these challenges, this project involves creating high-level programming frameworks with highly-optimized backends to make it easier for non-experts to write high-performance parallel programs for graphs and hypergraphs dealing with static and streaming data. This project also involves designing parallel algorithms that are efficient both in theory and in practice, so that they can perform well under all possible inputs and across many machine parameters, and scale gracefully to larger data sets. Using the resulting algorithms and frameworks, scientists will be able to use high-level tools to perform graph and hypergraph analytics on massive inputs much more efficiently than before, both in theory and in practice.This project involves designing new parallel primitives and algorithms for many fundamental graph and hypergraph problems that are fast and memory-efficient, both in theory and in practice. The new algorithms are being evaluated on the largest publicly-available data sets using large-scale multicore machines. The project also involves creating high-level abstractions and programming frameworks to support the implementation of theoretically-efficient algorithms on both static and streaming data. First, a domain specific language for graph computations that generates efficient and highly-optimized code from high-level specifications of algorithms and optimizations will be designed. Second, a unified framework for streaming graph analytics that can efficiently support parallel updates to the graph (simultaneously running algorithms and updates), incremental algorithms, and temporal analysis will be developed. Finally, a novel abstraction and framework for hypergraph processing that will support theoretically-efficient implementations of hypergraph algorithms will be designed. The results will lead to fundamental advances in parallel algorithm design and programming frameworks for graph and hypergraph analytics.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.