CAREER: Algorithm-Centric High Performance Graph Processing

Purdue University, West Lafayette IN

Investigators

Abstract

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.