CAREER: Algorithmic and Software Foundations for Large-Scale Graph Analysis

提出的研究旨在为现代数据集和新兴并行平台上的大型基于图的计算设计高效可扩展的算法。图抽象和图论计算在分析来自实验设备、医疗数据集、来自网络和移动设备的社会生成数据以及科学模拟数据的数据中起着至关重要的作用。该提案旨在通过创建新的算法框架，提供对并行图分析的基本理解。受目前在基因组学、蛋白质组学和社会网络分析方面的万亿级应用的推动，该项目将承担四种算法框架的全新设计，以捕获广泛的基于图的计算类别：基于遍历的静态图计算、动态图分析、子图枚举和模式搜索计算，以及多尺度和多层次图计算。这项研究将导致新的内存高效图形表示和数据结构的设计，基于数据分区的新型线性时间并行算法策略的创建，以及对影响图形处理效率和可扩展性的架构特征的更深入理解。预期的结果是使非并行计算专家能够在比当前最先进的抽象和性能更高的数量级上设计图形分析。拟议的教育活动与研究目标密切相关，试图在宾夕法尼亚州立大学营造跨学科计算研究的环境。关于并行图分析、计算生物学并行算法和高性能社会数据挖掘的新研究生课程将促进学生参与该项目及其合作者的当前研究活动。识别新的高层次的以数据为中心的并行算法和软件设计原则将是一个关键的更广泛的影响结果。该项目将积极与依赖基于图形的分析的学术、工业和政府实验室合作伙伴合作，在开源许可下发布算法框架，并通过虚拟研讨会和教程培训从业者和跨学科团队。

The proposed research aims at designing highly efficient and scalable algorithms for large graph-based computations on modern data sets and emerging parallel platforms. Graph abstractions and graph-theoretic computations play a critical role in the analysis of data from experimental devices, medical data sets, socially-generated data from the web and mobile devices, and scientific simulation data. The proposal aims to provide a fundamental understanding of parallel graph analytics, with the creation of novel algorithmic frameworks. Motivated by current terascale applications in genomics, proteomics, and social network analytics, the project will undertake the clean-slate design of four algorithmic frameworks that capture broad classes of graph-based computations: traversal-based static graph computations, dynamic graph analytics, subgraph enumeration and pattern search computations, and multiscale and multilevel graph computations. This research will lead to the design of new memory-efficient graph representations and data structures, the creation of novel linear time parallel algorithmic strategies based on data partitioning, and a deeper understanding of architectural features that impact graph processing efficiency and scalability. The expected outcome is to enable non-parallel computing experts design graph analytics at orders-of-magnitude higher levels of abstraction and performance than the current state-of-the-art.The proposed educational activities, closely related to the research goals, attempt to foster an environment of interdisciplinary computational research within Penn State. New graduate classes on parallel graph analysis, parallel algorithms for computational biology, and high-performance social data mining, will facilitate student involvement in current research activities of this project and its collaborators. The identification of new high-level data-centric parallel algorithm and software design principles will be a key broader impacts outcome. The project will actively collaborate with academic, industrial, and government laboratory partners that rely on graph-based analytics, release the algorithmic frameworks under open-source licenses, and train practitioners and interdisciplinary teams through virtual workshops and tutorials.