CAREER: Algorithm-Centric High Performance Graph Processing

随着大数据的出现，大量数据从众多来源收集，例如社交媒体，传感器馈送和科学实验。图分析已经成为理解异构数据类型之间关系的重要方法，允许数据分析师从数据中的模式中获得有价值的见解，用于广泛的应用，包括机器学习任务，自然语言处理，异常检测，聚类，推荐，社会影响分析，生物信息学。由于其广泛的应用，研究界从多个角度来处理图处理，包括分布式，基于磁盘的系统和内存中的图处理。当前图处理研究存在4个主要问题：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.