AKIN: A Streaming Graph Partitioning Algorithm for Distributed Graph Storage Systems
AKIN: A Streaming Graph Partitioning Algorithm for Distributed Graph Storage Systems
复制标题
DOI：
10.1109/ccgrid.2018.00033
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Wei Zhang-;Yong Chen;Dong Dai
中科院分区：
文献类型：
--
作者：
Wei Zhang-;Yong Chen;Dong Dai
许多与图相关的应用程序面临着在分布式环境中管理过多且不断增长的图数据的挑战。因此，有必要考虑一种图划分算法，以便在数据进入时将图数据分发到多台机器上。平衡数据分布和最小化割边率是图划分问题的两个基本目标。虽然实现流图的平衡分区很容易，但现有的图分区算法要么无法在流工作负载上工作，要么留下边缘切割率有待进一步提高。我们的研究旨在提供一个更好的解决方案，适合在分布式系统中的流图划分的需要，进一步降低边切割率，同时保持所有分区之间的粗略平衡。我们利用顶点度的相似性度量来尽可能多地将结构相关的顶点聚集在同一分区中，这与最先进的流图分区算法FENNEL相比进一步降低了边切割率。我们的评估表明，我们的流图分割算法能够实现更好的分割质量方面的边缘切割率（高达20%的减少相比，FENNEL），同时保持体面的所有分区之间的平衡，这种改进适用于各种现实生活中的图形。
Many graph-related applications face the challenge of managing excessive and ever-growing graph data in a distributed environment. Therefore, it is necessary to consider a graph partitioning algorithm to distribute graph data onto multiple machines as the data comes in. Balancing data distribution and minimizing edge-cut ratio are two basic pursuits of the graph partitioning problem. While achieving balanced partitions for streaming graphs is easy, existing graph partitioning algorithms either fail to work on streaming workloads, or leave edge-cut ratio to be further improved. Our research aims to provide a better solution that fits the need of streaming graph partitioning in a distributed system, which further reduces the edge-cut ratio while maintaining rough balance among all partitions. We exploit the similarity measure on the degree of vertices to gather structuralrelated vertices in the same partition as much as possible, this reduces the edge-cut ratio even further as compared to the state-of-the-art streaming graph partitioning algorithm - FENNEL. Our evaluation shows that our streaming graph partitioning algorithm is able to achieve better partitioning quality in terms of edge-cut ratio (up to 20% reduction as compared to FENNEL) while maintaining decent balance between all partitions, and such improvement applies to various real-life graphs.