Blogel: Thinking Beyond the Perspective of a Vertex

Blogel is not designed as yet another Pregel-like system. We decided to develop Blogel since we find through our experience of using Pregel-like systems that, the vertex-computing framework sometimes has poor performance in processing large real world graphs.

For example, social networks and web graphs usually have (1)skewed degree distribution and (2)(relatively) high density, while spatial networks have a (3)large diameter.

Blogel extends Pregel with a block-computing functionality, which naturally handles all the three adverse graph characteristics. Blogel programmers may think like a block and develop efficient algorithms for various graph problems.

A central issue of applying block-computing is whether there exists efficient parallel algorithms to partition an arbitrary graph into blocks, so that block-centric programs can then run over these blocks. We propose partitioning algorithms that works by vertex-computing, which partitions the input graph into blocks highly efficiently. Furthermore, the blocks are of high quality and allow a very balanced workload among machines in the cluster.

Blogel is able to achieve orders of magnitude performance improvements over the state-of-the-art distributed graph computing systems.