科研之友
微信
新浪微博
Facebook
分享链接
摘要
图划分算法是分布式图计算系统里的重要组成部分,它将一个图划分为若干子图以便在分布式系统中运行,并将子图上的点和边数据及子图上的计算任务分配到各分区.异质图是现实世界中广泛存在的一种图,它是指具有多种节点类型或边类型的图,在针对异质图的计算过程中,现有的图划分算法对于异质图的处理没有考虑到以下问题:在图计算过程中,不同类型的节点和边携带的数据量可能不同;不同的节点和边类型,可能会采用不同的处理算法,其计算时间也会不同.针对现有图划分方法的不足,本文提出一种面向异质图的在线图划分算法OGP-HG算法,并对现有的Graph X图计算引擎进行改进,将OGP-HG算法在改进后的图计算引擎中实现.本文提出的OGP-HG算法通过计算节点划分到不同分区上的负载均衡得分和边划分到不同分区上的数据均衡得分,得到使异质图负载和内存占用均衡的划分结果.实验表明,与传统图划分算法相比,该算法提高异质图计算效率1.05–1.4倍.
- 单位
