CAREER: Parallel Algorithms and Frameworks for Graph and Hypergraph Processing

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Graphs are a tool used to model the interactions between various entities. Efficiently processing large graphs has attracted significant attention due to its applications in various domains, such as biology, chemistry, and social network analysis. With the explosion in the volume of data, graphs have become very large and can contain hundreds of billions of vertices and trillions of edges. Various applications also benefit from modeling the underlying data as a hypergraph, which enables relationships among multiple entities to be represented better than a graph. In addition, many of these data sets are changing rapidly in real-time and applications require computing results on the latest data. It is crucial to design high-performance parallel algorithms to enable analysis to be done on graphs and hypergraphs in a timely fashion. However, writing efficient parallel code is notoriously difficult. Furthermore, many parallel algorithms used in practice today do not have strong theoretical guarantees, causing them to perform extremely poorly on certain inputs. To address these challenges, this project involves creating high-level programming frameworks with highly-optimized backends to make it easier for non-experts to write high-performance parallel programs for graphs and hypergraphs dealing with static and streaming data. This project also involves designing parallel algorithms that are efficient both in theory and in practice, so that they can perform well under all possible inputs and across many machine parameters, and scale gracefully to larger data sets. Using the resulting algorithms and frameworks, scientists will be able to use high-level tools to perform graph and hypergraph analytics on massive inputs much more efficiently than before, both in theory and in practice. This project involves designing new parallel primitives and algorithms for many fundamental graph and hypergraph problems that are fast and memory-efficient, both in theory and in practice. The new algorithms are being evaluated on the largest publicly-available data sets using large-scale multicore machines. The project also involves creating high-level abstractions and programming frameworks to support the implementation of theoretically-efficient algorithms on both static and streaming data. First, a domain specific language for graph computations that generates efficient and highly-optimized code from high-level specifications of algorithms and optimizations will be designed. Second, a unified framework for streaming graph analytics that can efficiently support parallel updates to the graph (simultaneously running algorithms and updates), incremental algorithms, and temporal analysis will be developed. Finally, a novel abstraction and framework for hypergraph processing that will support theoretically-efficient implementations of hypergraph algorithms will be designed. The results will lead to fundamental advances in parallel algorithm design and programming frameworks for graph and hypergraph analytics. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.