先进数据系统实验室

　　我们实验室的自主完成的两个维度均衡的图划分算法BPart被计算机系统领域会议ICPP（CCF B类）收录。

　　论文：

　　论文题目：Towards Fast Large-scale Graph Analysis via Two-dimensional Balanced Partitioning

　　论文摘要：

　　分布式图计算系统需要将一个大图划分为多个子图，并将这些子图加载到集群中不同机器中进行计算。子图划分的好坏会极大的影响分布式图计算系统的计算效率。比如划分的均衡性(包括节点和边两个维度均衡)会极大影响分布式图计算的负载均衡；划分跨子图边数量会极大影响分布式图计算的通信开销。然而当前分布式图计算系统中采用的图划分算法通常只能实现节点均衡或者边均衡，或者能够实现两个维度均衡的算法，其跨子图边数量非常多。因此，在进行子图划分时，需要保证节点和边都划分均衡的同时尽可能地减小跨子图边地数量。

　　在本文中，我们提出保证节点和边两个维度均衡的划分算法BPart。他的核心思想是，首先将大图划分为多个小的子图，其数量远大于集群中机器的数量，并且在划分时通过设计复合的均衡性指标，使得每个子图中节点和边数量满足反比的关系；然后将这些小的子图按照节点或者边数量排序，并头尾组合为一个大的子图。通过多次的组合，BPart可以实现两个节点和边两个维度的划分均衡。我们将BPart集成到两个当前最优的分布式图处理系统KnightKing和Gemini中，并研究他们在执行图算法时的计算效率。通过实验对比，采用BPart作为划分策略可以减小不同图算法5%-70%的运行时间。