Graph Twiddling in a MapReduce World

TLDR

Graph analysis is increasingly demanding, making scalable processing methods essential, and cloud computing offers attractive features for this purpose. The article investigates whether graph operations can be decomposed into MapReduce cycles, thereby encouraging the use of cloud computing for graph processing. The authors propose dispersing large graphs across networked computers using MapReduce operations, and also enabling single‑machine streaming processing for graphs that exceed memory limits.

Abstract

As the size of graphs for analysis continues to grow, methods of graph processing that scale well have become increasingly important. One way to handle large datasets is to disperse them across an array of networked computers, each of which implements simple sorting and accumulating, or MapReduce, operations. This cloud computing approach offers many attractive features. If decomposing useful graph operations in terms of MapReduce cycles is possible, it provides incentive for seriously considering cloud computing. Moreover, it offers a way to handle a large graph on a single machine that can't hold the entire graph as well as enables streaming graph processing. This article examines this possibility.