Large-scale Graph Analysis in Data-Centric Models like MapReduce

Ananth Grama

Dept. of Computer Science, Purdue University

Science of Information Purdue University

Outline

Web-scale graph-structured datasets require distributed processing Most graph algorithms are a series of matrix-vector multiplications Optimal implementation of a single mat-vec in MapReduce Optimizations across iterations

Asynchronous algorithms through Relaxed Synchronization Speculative parallelism through TransMR (transactional MapReduce) Locking techniques for efficient distribution transactions

Future Work

Large-scale graph analysis

Dataset characteristics

Massive distributed graph-structured datasets Graphs with billions of nodes, running into petabytes of storage (e.g., web graphs and social networks)

Application characteristics

Most graph algorithms can be modeled as a series of matrix-vector products (mat-vecs) e.g., PageRank, Shortest-path problems, etc. Each mat-vec requires distributed execution Algorithmic efficiency achieved through asynchrony and amorphous data-parallelism

MapReduce for scalable, distributed execution of each mat-vec