动态图划分算法研究综述
作者:
作者单位:

作者简介:

通讯作者:

李贺,E-mail:heli@xidian.edu.cn

中图分类号:

基金项目:

国家自然科学基金(61602354,61876138);四川省科技计划项目(2021JDJQ0021,2022YFG0186);成都市技术创新研发项目(2021-YF05-00491-SN);成都市重大科技创新项目(2021-YF08-00156-GX);成都市“揭榜挂帅”科技项目(2021-YF08-00156-GX);中央高校基本科研业务费专项资金


Research on Dynamic Graph Partitioning Algorithms: A Survey
Author:
Affiliation:

Fund Project:

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

    图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据的规模不断增长,真实世界中的图表现出动态性,如何对动态图进行划分已成为目前图划分研究的热点问题.本文从不同的动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先,介绍图划分的三种不同的划分策略及问题定义,图的两种不同的动态性来源以及动态图划分问题.然后,介绍三种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法.其次,介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法.再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法.最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.

    Abstract:

    Graph partitioning is the primary work of large-scale distributed graph processing, which plays a fundamental role in storage, query, processing and mining of graph applications. Since graph data in the real world are always dynamic, the research of dynamic graph partitioning is a hot topic. This paper systematically introduces the current algorithms for dynamic graph partitioning, which including streaming graph partitioning algorithm, incremental graph partitioning algorithm, and graph repartitioning algorithm. Firstly, the paper introduces three different partitioning strategies, two different dynamic sources of graph and dynamic graph partitioning problem. Then, three different streaming graph partitioning algorithms are introduced, including Hash algorithm, neighbor distribution-based algorithm and novel algorithm. Secondly, two different incremental graph partitioning algorithms, single element incremental graph partitioning, and batch incremental graph partitioning are introduced. Thirdly, the repartitioning algorithm for graph structure and the repartitioning algorithm for graph computation are introduced, respectively. Finally, based on the analysis and comparison of the existing methods, the main challenges of dynamic graph partitioning are summarized and the corresponding research problems are proposed.

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

李贺,刘延娜,袁航,杨舒琪,韵晋鹏,乔少杰,黄健斌,崔江涛.动态图划分算法研究综述.软件学报,,():0

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-12-11
  • 最后修改日期:2022-05-09
  • 录用日期:
  • 在线发布日期: 2022-07-22
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号