基于GPS平台的高效k-bisimulation计算算法
CSTR:
作者:
作者单位:

(1.黑龙江大学 计算机科学技术学院,哈尔滨 150080;2.哈尔滨工业大学 计算机科学与技术学院, 哈尔滨 150001)

作者简介:

阚忠良(1969—),男,博士研究生,副教授; 李建中(1950—),男,教授,博士生导师; 王宏志(1978—),男,教授,博士生导师

通讯作者:

李建中,lijzh@hit.edu.cn.

中图分类号:

TP311

基金项目:

国家科技支撑计划项目(2015BAH10F01);国家自然科学基金项目(U6,9)


GPS-based algorithms for efficient k-bisimulation computation
Author:
Affiliation:

(1. School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China; 2. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    计算图的互模划分在许多应用领域中起着至关重要的作用.图中两个点是互模的当且仅当这两点具有相同的特征.随着图数据规模的增大,传统的运行在单机上的互模划分算法面临着越来越大的挑战,分布式算法以及并行算法则成为提高图计算可扩展性的重要途径.最近研究人员提出两种基于MapReduce计算模型的分布式互模划分算法,算法均计算图的局部互模划分.采用MapReduce计算模型的分布式互模划分算法具有网络通讯代价高昂的问题,每次MapReduce迭代操作均会将整个图中所有点边的状态通过网络传输,重新为点边分配计算节点,但实际上计算点的局部互模划分特征仅需要局部信息.以此为研究出发点,本文提出了基于分布式图数据处理平台的互模划分算法,仅使用点的局部信息来计算其特征,进而提升计算效率.经过实验验证,本文算法可以大幅度减少算法执行过程中的网络数据传输量.在包含数亿边大图上的实验表明,在未经图的预处理的情况下,本文算法的时间效率提升了7~16倍,有效的解决了MapReduce计算模型带来的网络通讯代价高昂的问题.

    Abstract:

    Computing the bisimulation partition of a graph plays a key role in various application areas. Two nodes are bisimular if and only if they obtain the same signature. Faced with a big graph, traditional in-memory algorithms can hardly meet practical need. Recently, researchers have proposed two kinds of MapReduce based distributed algorithms to handle bisimulation partition on the big graph, both calculating localized bisimulation. MapReduce based algorithms suffer from huge network communication burden, at the meantime, we only need local information to calculate the signature of a node. Motivated by these observations, we propose an algorithm based on a graph processing system that only uses local information to calculate the signature of a node. We argue that our algorithm can make considerable reduction on the network transportation during computation. In the experiment calculated on the big graph which contains billions of edges, our algorithm can be seven to sixteen times faster even without graph pre-partition.

    参考文献
    相似文献
    引证文献
引用本文

阚忠良,李建中,徐俊,王宏志.基于GPS平台的高效k-bisimulation计算算法[J].哈尔滨工业大学学报,2018,50(5):173. DOI:10.11918/j. issn.0367-6234.201711054

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-11-12
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2018-04-27
  • 出版日期:
文章二维码