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.