| 面向异质图的在线图划分算法 |
| |
| 引用本文： | 赵新朋,罗雄飞,陈楚依,鄢宝彤,乔颖.面向异质图的在线图划分算法[J].计算机系统应用,2023,32(12):143-151. |
| |
| 作者姓名： | 赵新朋 罗雄飞 陈楚依 鄢宝彤 乔颖 |
| |
| 作者单位： | 中国科学院 软件研究所, 北京 100190 |
| |
| 基金项目： | 中国科学院战略先导C类课题（XDC02030300） |
| |
| 摘 要： | 图划分算法是分布式图计算系统里的重要组成部分, 它将一个图划分为若干子图以便在分布式系统中运行, 并将子图上的点和边数据及子图上的计算任务分配到各分区. 异质图是现实世界中广泛存在的一种图, 它是指具有多种节点类型或边类型的图, 在针对异质图的计算过程中, 现有的图划分算法对于异质图的处理没有考虑到以下问题: 在图计算过程中, 不同类型的节点和边携带的数据量可能不同; 不同的节点和边类型, 可能会采用不同的处理算法, 其计算时间也会不同. 针对现有图划分方法的不足, 本文提出一种面向异质图的在线图划分算法OGP-HG算法, 并对现有的GraphX图计算引擎进行改进, 将OGP-HG算法在改进后的图计算引擎中实现. 本文提出的OGP-HG算法通过计算节点划分到不同分区上的负载均衡得分和边划分到不同分区上的数据均衡得分, 得到使异质图负载和内存占用均衡的划分结果. 实验表明, 与传统图划分算法相比, 该算法提高异质图计算效率1.05–1.4倍.
|
| 关 键 词： | 异质图 图计算 图划分 负载均衡 内存优化 |
| 收稿时间： | 2023/5/10 0:00:00 |
| 修稿时间： | 2023/6/14 0:00:00 |
Online Graph Partitioning Algorithm for Heterogeneous Graphs |
| |
| ZHAO Xin-Peng,LUO Xiong-Fei,CHEN Chu-Yi,YAN Bao-Tong,QIAO Ying.Online Graph Partitioning Algorithm for Heterogeneous Graphs[J].Computer Systems& Applications,2023,32(12):143-151. |
| |
| Authors: | ZHAO Xin-Peng LUO Xiong-Fei CHEN Chu-Yi YAN Bao-Tong QIAO Ying |
| |
| Affiliation: | Institute of Software, Chinese Academy of Sciences, Beijing 100190, China |
| |
| Abstract: | |
| |
| Keywords: | heterogeneous graph graph computing graph partitioning load balance memory optimization |
|
| 点击此处可从《计算机系统应用》浏览原始摘要信息 |
|
点击此处可从《计算机系统应用》下载全文 |
|
