swMATH ID: 41763
Software Authors: Yan, D., Cheng, J., Lu, Y., Ng, W.
Description: Blogel: a block-centric framework for distributed computation on real-world graphs. The rapid growth in the volume of many real-world graphs (e.g., social networks, web graphs, and spatial networks) has led to the development of various vertex-centric distributed graph computing systems in recent years. However, real-world graphs from different domains have very different characteristics, which often create bottlenecks in vertex-centric parallel graph computation. We identify three such important characteristics from a wide spectrum of real-world graphs, namely (1)skewed degree distribution, (2)large diameter, and (3)(relatively) high density. Among them, only (1) has been studied by existing systems, but many real-world power-law graphs also exhibit the characteristics of (2) and (3). In this paper, we propose a block-centric framework, called Blogel, which naturally handles all the three adverse graph characteristics. Blogel programmers may think like a block and develop efficient algorithms for various graph problems. We propose parallel algorithms to partition an arbitrary graph into blocks efficiently, and block-centric programs are then run over these blocks. Our experiments on large real-world graphs verified that Blogel is able to achieve orders of magnitude performance improvements over the state-of-the-art distributed graph computing systems.
Homepage: http://www.vldb.org/pvldb/vol7/p1981-yan.pdf
Related Software: Pregel; GPS; Giraph; GraphLab; SympleGraph; Mermaid; PathGraph; NScaleSpark; Gluon; Graphalytics; GossipMap; GoFFish; Fregel; Apache Spark; HaLoop; Elixir; Green-Marl; PowerGraph; GraphX; Nethogs
Referenced in: 3 Publications

Referencing Publications by Year