【摘要】 在大规模图数据的分布式处理中,往往需要将图数据进行划分并放置在不同的节点上。如果数据划分得不均衡,那么部分节点可能会成为分布式系统的瓶颈。为了提高图数据划分的均衡性,并且有效地应对图数据的快速更新,提出了一种松弛的优化均衡流式图划分算法。首先,定义了一种同时包含划分内部代价和划分之间的割的代价的目标函数作为图划分的整体框架。然后,在图划分框架的基础上通过最大化和最小化两种优化函数分析了均衡图划分问题,并给出了二者之间的关系。最后,针对流式图数据,提出一种贪婪的图最优k划分算法。该划分算法以最大化优化函数为基础,通过最大化顶点放置产生的目标函数增加值进行节点划分块的选取。实验表明,提出的图划分算法与相关算法相比,不仅均衡性好,而且通信开销小,在基于该算法进行图划分时上层应用的计算性能得到了明显的提高。更多还原

【Abstract】 During the distributed processing of large scale graph data,it usually needs to partition the whole graph into different nodes.If the partition isn’t balanced,some of the nodes may be the bottleneck of the distributed system.In order to achieve a balanced partition and handle the quick updates of graph efficiently,this paper proposed a relaxed optimal balanced streaming graph partitioning algorithm.Firstly,we defined an objective function including costs of both inter-partitions and intra-partition as the general graph partition framework.Secondly,we analyzed the graph partition problem according to a maximal and a minimal optimization functions based within the proposed framework,and gave their relationships.Finally,we proposed a greedy optimal graph k-partitions algorithm upon the streaming graph.The experiments show that,the proposed graph partitioning algorithm have better balance and lower communication cost than related works,and upper applications upon this algorithm have better performance.更多还原