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

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

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.