Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs

マイクロソフトの新たなグラフ処理の論文。

Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs
http://research.microsoft.com/pubs/155533/paper.pdf

Many phenomena and artifacts such as road networks, social networks and the web can be modeled as large graphs and analyzed
using graph algorithms. However, given the size of the underlying
graphs, efficient implementation of basic operations such as connected component analysis, approximate shortest paths, and linkbased ranking (e.g.PageRank) becomes challenging.
This paper presents an empirical study of computations on such
large graphs in three well-studied platform models, viz., a relational
model, a data-parallel model, and a special-purpose in-memory
model. We choose a prototypical member of each platform model
and analyze the computational efficiencies and requirements for
five basic graph operations used in the analysis of real-world graphs
viz., PageRank, SALSA, Strongly Connected Components (SCC),
Weakly Connected Components (WCC), and Approximate Shortest Paths (ASP). Further, we characterize each platform in terms of
these computations using model-specific implementations of these
algorithms on a large web graph. Our experiments show that there
is no single platform that performs best across different classes of
operations on large graphs. While relational databases are powerful and flexible tools that support a wide variety of computations,
there are computations that benefit from using special-purpose storage systems and others that can exploit data-parallel platforms