Blogel
Authors:
Open Access
- 1 October 2014
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 7 (14) , 1981-1992
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Pregel algorithms for graph connectivity problems with performance guaranteesProceedings of the VLDB Endowment, 2014
- From "think like a vertex" to "think like a graph"Proceedings of the VLDB Endowment, 2013
- Fast iterative graph computation with block updatesProceedings of the VLDB Endowment, 2013
- Accelerate large-scale iterative computation through asynchronous accumulative updates2012
- Efficient processing of distance queries in large graphs2012
- Truss decomposition in massive networksProceedings of the VLDB Endowment, 2012
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Network structure and minimum degreeSocial Networks, 1983
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969