CAREER: Algorithm-Centric High Performance Graph Processing

随着大数据的出现，从社交媒体、传感器馈送和科学实验等多种来源收集了大量数据。图形分析已经成为理解不同类型数据之间关系的一种重要方式，使数据分析人员能够从数据中的模式中获得有价值的见解，用于广泛的应用，包括机器学习任务、自然语言处理、异常检测、聚类、推荐、社会影响分析、生物信息学。由于图形处理的广泛应用，研究界从多个角度对图形处理进行了研究，包括分布式、基于磁盘的系统和内存中的图形处理。目前的图形处理研究存在四个关键问题：1)编程模型和算法之间的差距；2)所研究的应用缺乏多样性；3)对动态图形和图形数据库的研究不足；4)体系结构支持只关注经典问题。本研究提出了一种以算法为中心的高性能图形处理新方法ALCHEM，涉及算法、编程模型、系统和体系结构的协同设计。这一跨学科研究计划利用机会探索或加强不同层之间的交互，重点放在算法效率上。它包含四个研究方向：(1)使用图抽象作为编程模型和算法之间的桥梁，以加快收敛速度；(2)开发具有专门化的高效执行模型；(3)建立图形数据库，作为关系和动态图形数据的统一引擎；(4)以新的特征增强体系结构，以支持新的图形算法(如随机游走)。这项研究将引发研究人员在理论、系统和架构方面的密切互动。该项目将吸引妇女、少数民族和本科生。独具特色的是，它不仅可以训练学生的系统构建技能，还可以加强他们对算法的理解。研究成果将通过更好和更快的建议、增强的安全性和更好的社会关系来改善日常生活，从而造福社会。

With the advent of big data, large amounts of data are collected from numerous sources, such as social media, sensor feeds, and scientific experiments. Graph analytics has emerged as an important way to understand the relationships between heterogeneous types of data, allowing data analysts to draw valuable insights from patterns in the data for a wide range of applications, including machine learning tasks, natural language processing, anomaly detection, clustering, recommendation, social influence analysis, bioinformatics. Due to the broad applications, the research community tackled graph processing from multiple angles, including distributed, disk-based systems and in-memory graph processing. There are four key problems of today's graph processing research: 1) the gap between programming model and algorithm; 2) the lack of diversity in applications studied; 3) insufficient research on dynamic graphs and graph database; and 4) architectural supports focus only on classical problems. This proposal attempts to advance the graph processing systems by solving these major challenges.This research proposes a novel approach ALCHEM, algorithm-centric high performance graph processing, which involves the collaborative designs of algorithms, programming model, systems, and architecture. This interdisciplinary research program takes the opportunity to explore or enhance the interactions between different layers, with the emphasis on algorithm efficiency. It contains four research thrusts: (1) Using graph abstraction as a bridge between programming model and algorithm to speed up the convergence; (2) Developing efficient execution model with specialization; (3) Building a graph database as a unified engine for relational and dynamic graph data; (4) Enhancing architecture with novel features to support new graph algorithms (e.g., random walk). The research will trigger close interactions between researchers in theory, system, and architecture. The project will engage women, minorities and undergraduates. Uniquely, it will not only train the students' system building skills, but also strengthen their algorithm understanding. The research outcomes will benefit the society by improving everyday life with better and faster recommendations, enhanced security, and better social relationships.