Graph Partitioner

原创
2016/05/26 14:51
阅读数 46

一. Graph Voronoi Diagram Partitioner[1]

The GVD computation can be easily implemented in the vertex- centric computing model, by performing multi-source BFS. Specif- ically, in superstep 1, each source s sets block(s) = s and broad- casts it to the neighbors; for each non-source vertex v, block(v) is unassigned. Finally, the vertex votes to halt. In superstep i (i > 1), if block(v) is unassigned, v sets block(v) to an arbitrary source received, and broadcasts block(v) to its neighbors before voting to halt. Otherwise, v votes to halt directly. When the process con- verges, we have block(v) = si for each v ∈ V C(si).

输入图片说明

二. Coarsening[2]

reference

[1] Zhou, Yang, Liu, Ling, Lee, Kisung, & Zhang, Qi. (2015). Graphtwist: fast iterative graph computation with two-tier optimizations. Proceedings of the Vldb Endowment, 8(11), 1262-1273. [2]

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部