Design Patterns for Efficient Graph Algorithms in MapReduce Authors: Jimmy Lin and Michael Schatz
Abstract:
Graphs are analyzed in many important contexts, including ranking search results based on the hyperlink structure of the world wide web, module detection of proteinprotein interaction networks, and privacy analysis of social networks. Many graphs of interest are difficult to analyze because of their large size, often spanning millions of vertices and billions of edges. As such, researchers have increasingly turned to distributed solutions. In particular, MapReduce has emerged as an enabling technology for large-scale graph processing. However, existing best practices for MapReduce graph algorithms have significant shortcomings that limit performance, especially with respect to partitioning, serializing, and distributing the graph. In this paper, we present three design patterns that address these issues and can be used to accelerate a large class of graph algorithms based on message passing, exemplified by PageRank. Experiments show that the application of our design patterns reduces the running time of PageRank on a web graph with 1.4 billion edges by 69%.
I wonder if the partitioning into similar domains (their term with no prompting from me) would have the same impact on merging in a topic map?
[…] This post was mentioned on Twitter by Félix Averlant and Phaneesh Nagaraja, Patrick Durusau. Patrick Durusau said: Design Patterns for Efficient Graph Algorithms in MapReduce, http://bit.ly/igYRgH […]
Pingback by Tweets that mention Design Patterns for Efficient Graph Algorithms in MapReduce « Another Word For It -- Topsy.com — February 3, 2011 @ 5:08 am