图划分是大规模分布式图处理的首要工作, 对图应用的存储、查询、处理和挖掘起基础支撑作用. 随着图数据规模的不断扩大, 真实世界中的图表现出动态性. 如何对动态图进行划分, 已成为目前图划分研究的热点问题. 从不同动态图划分算法的关注点和特点出发, 系统性地介绍当前可用于解决动态图划分问题的各类算法, 包括流式图划分算法、增量式图划分算法和图重划分算法. 首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题; 然后介绍3种不同的流式图划分算法, 包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法; 其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法; 再次, 分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法; 最后, 在对已有方法分析和比较的基础上, 总结目前动态图划分面临的主要挑战, 提出相应的研究问题.
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 study 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 study 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.
近年来, 随着互联网信息技术的迅猛发展, 各行各业每时每刻都在产生着各种各样的数据. 图作为一种特殊的数据结构, 不但可以存储数据个体本身, 还可以存储数据个体之间复杂的关联关系, 吸引了学术界和工业界的广泛关注. 真实数据集的来源非常广泛, 除了一些网站[
图划分是分布式图处理的基础工作, 其作用是将一个大规模图数据划分到一个集群中的不同机器上. 在分布式图处理系统中, 根据短板效应, 集群的处理速度取决于其中运行最慢的机器, 这就需要集群中各个机器的工作负载应该尽可能相同. 同时, 图处理任务需要沿着图的拓扑结构进行, 这使得一个机器中的某些顶点需要与其他机器中的邻居顶点通过传递消息进行通信. 由于网络带宽和网络延迟等因素, 集群中不同机器之间的通信代价和通信时间要远远高于单个机器内部的通信成本, 且不同机器之间的通信受网络性能的影响而具有不稳定性, 这就需要集群中不同机器之间的通信成本要尽可能地低. 因此, 分布式图计算的性能主要由运行最慢的机器和不同机器之间的通信成本决定. 所以, 图划分的质量对分布式图处理的性能有很大的影响, 其目标是在集群中各个机器负载平衡的基础上, 最小化不同机器之间的通信成本.
基于负载平衡和最小化通信成本这两个基础目标, 很多不同的图划分算法被提出. 最早的划分算法主要是针对静态图的, 如谱划分算法[
现有的动态图划分算法与静态图划分算法有着明显的区别: 一是动态图划分算法通常可以重用初始划分的信息, 从而减少动态划分的开销, 这也是动态图划分对比静态图划分的优势; 二是图的动态性是持续的, 所以动态图划分算法的开销不能过大. 因此, 利用静态图划分算法重头开始来处理动态图是不可行的. 目前, 可用于划分动态图的划分算法从不同的关注点和特点出发, 主要可分为流式动态图划分算法、增量式图划分算法和图重划分算法. 这样的分类依据主要是由于流式动态图划分算法的主要特点是能够实时地依次处理单个顶点或者边, 它能够以较高的算法效率处理不断变化的动态图. 但大部分的流式动态图划分算法过于追求低的划分时间和划分成本, 因而获得了较低的划分质量. 此外, 大部分流式图划分算法最初被提出是针对大规模图划分的. 增量式图划分算法与图重划分算法的主要区别在于: 增量式图划分算法提出了专注于处理动态变化的那部分图数据, 对动态变化部分提出了划分策略; 而图重划分算法则假设图发生动态变化已经导致分区发生了变化, 它更专注于通过动态调整不断优化分区, 从而获得高质量的划分结果.
动态图划分算法分类
本文在对近年来动态图划分问题的研究进程进行跟踪分析的基础上, 对该问题的相关工作进行了深入的分析、总结和归纳. 第1节概述图划分的背景. 第2节介绍流式动态图划分算法. 第3节介绍增量式图划分算法. 第4节介绍图重划分算法. 第5节对动态图划分问题的研究进行总结和分析, 讨论其面临的挑战, 并展望未来的研究方向.
图划分是一个经典的NP难问题, 最初在文献[
一个图由顶点和边构成, 因此划分一个图的基本方式主要有顶点划分和边划分两种. 顾名思义, 顶点划分是将图中的顶点划分成多个分区, 若边的两个端点被划分到两个不同的分区, 则该边被切割, 因此, 顶点划分也被称为基于边割的图划分.
顶点划分与边划分
边划分的提出是为了解决顶点划分的缺陷, 最初, 分布式图处理系统使用的是顶点划分, 例如Pregel、Giraph、GraphLab等. 在这些系统中, 被切割的边需要存储在其端点所在的两个分区中, 这导致每个顶点的计算负载都集中在一个分区内, 具有较强的局部性. 而在真实应用中, 图的度通常都呈幂律分布, 即大多数顶点只有相对较少的邻居, 而少数顶点有非常多的邻居, 例如社交网络中的明星和普通人, 一般来说, 明星有很多人关注, 而普通人有很少的人关注. 在幂律度分布下, 顶点的度为
早期的像Pregel、Giraph和GraphLab的图并行系统通过切割边划分一个图以均匀地分配顶点, 这些基于顶点划分的分布式图处理系统会遭受高度顶点所带来的不平衡的计算和通信负载. 由此, 像PowerGraph和GraphX的图并行系统通过切割顶点以均匀地在多个机器上分配边, 尽管边划分减轻了高度顶点带来的不平衡问题, 但是基于边划分的系统对于低度顶点来说会招致较高的通信成本和过多的内存消耗. 因此, 最近, Powerlyra提出了混合切割策略来解决这个问题, 区别对待高度顶点和低度顶点. 具体地, 将高度顶点的边分配给所有机器来均匀分配计算负载, 以及将低度顶点划分到同一台机器以减少不必要的通信. 混合切割的划分方式是顶点划分方式和边划分方式的结合.
混合割划分
给定一个图
顶点划分的划分对象是图中的顶点集合
其中,
边划分的划分对象是图中的边集合
与顶点划分类似, 其中,
混合割划分对低度顶点和高度顶点的处理是不同的. 对于高度顶点, 混合割将高度顶点的邻边均匀划分到多个分区中, 这遵循点切割划分, 其主要目的是使得分区的负载尽可能地相等. 对于低度顶点, 混合割将低度顶点的邻边划分到同一分区, 这遵循边切割划分, 其主要目的是尽可能地减少不同分区间的通信. 在混合割中, 每个顶点通过哈希其ID分配给一个分区. 当一条边
针对静态图划分问题, 研究者们已经提出了大量的图划分算法, 主要可以分为基本图划分算法、多级图划分算法、分布式图划分算法以及其他类型图划分算法.
● 边切割
在基于边割的静态图划分算法中, 最经典的方法是Metis[
● 点切割
在基于点割的图划分中, 有些算法借鉴了基于边割的图划分方法, 如SBV[
● 混合切割
PowerLyra[
此外, 文献[
对于结构动态而言, 图
传统意义上的动态图指的是结构会发生动态变化的图, 如顶点和边的插入和删除, 而图结构的动态变化会破坏图的初始划分. 在真实应用中, 各个实体之间的关系以及实体本身都具有动态性. 例如, 如
图结构的动态性
随着分布式图处理系统的发展, 分布式图计算领域引申出了另一种动态图, 即动态图计算中的图. 图计算任务通常是迭代进行的, 而在每次迭代中, 各机器中只有部分活跃顶点参与实际的计算. 各机器中活跃顶点数量不一定相同, 且随着图计算的进行而动态变化, 这导致了图划分结果不匹配图计算的实际开销. 如
图计算的动态性
对于初始图
流式图划分算法被提出的初衷是, 以较低的开销划分一个静态图, 它将整个图视为一个顶点流或边流, 依次将每个顶点或每条边划分到分区中. 流式图划分算法的整个过程如
流式图划分算法思路框架图
基于Hash的算法使用一致的哈希函数将顶点或边映射到不同的分区. 例如, 在边划分中, 可以将边与分区间的映射函数定义为下式:
在设计合理的哈希函数下, 这可以使分区的负载几乎完全平衡. 基于Hash的算法效率较高, 且不需要图结构先验知识, 但它会导致大量的边割或点割.
● 边割
文献[
● 点割
在Hash思想的基础上, 有研究提出了一些改进的策略. DBH[
● 混合割
Powerlyra[
基于Hash的算法完全忽略了图的拓扑结构和历史划分信息, 因此会导致分区间存在大量的边割或点割.有一些研究利用新到达的顶点和边的邻居信息, 进一步提升了划分质量.
● 边割
LGD[
其中,
另一个很有代表性的流式顶点划分策略是Fennel[
其中,
● 点割
在流式边划分算法中, Powergraph提出了一个贪心策略Greedy[
1) Coordinated: 每个顶点所在的分区拥有全局信息;
2) Oblivious: 每个分区独自管理该分区中顶点, 信息不共享.
Coordinated的划分质量更高, 但需要更多的时间来进行分区间的通信.
HDRF[
其中,
其中,
● 混合割
受到Fennel的启发, Powerlyra[
其中,
上述基于Hash和基于邻居分布的算法均为单元素的流式算法, 即每次划分一个顶点或一条边. 在无法得知后续流信息的情况下, 为了平衡分区的负载, 一些顶点和边会违背贪心策略而被分配到负载较小的分区, 这也是流式算法的划分效果不如静态图划分算法的原因. 为了缓解这个弊端, 一些新颖的流式算法对单元素流的形式进行了改进, 主要可分为3种策略: 提前获取图信息、局部优化和分布式流.
● 边割
文献[
● 点割
Adwise[
● 混合割
为了在分布式图存储中实现低延迟和高吞吐量的在线查询, 文献[
流式图划分算法小结
类型 | 优点 | 缺点 | 划分方式 | 算法 | 特点 |
基于哈希的划分算法 | 算法效率高, 不需要图结构先验知识和历史划分信息 | 会导致大量的边割或点割 | 边割 | 文献[ |
根据每个顶点的ID, 将其映射到不同的分区中 |
点割 | DBH[ |
将边分配到度低的端点的Hash值对应的分区, 优先切割高度顶点 | |||
Grid, PDS[ |
将分区ID排列在网格中, 每条边根据端点的Hash值, 将端点映射到网格中. 利用网格辅助图划分 | ||||
混合割 | Powerlyra[ |
利用Hash对低度顶点进行散列, 将该顶点连同内边分配, 利用Hash散列高度顶点均匀分配所有内边给不同分区 | |||
基于邻居分布的划分算法 | 利用图的拓扑结构和历史划分信息, 相比基于Hash的方法获得更好的划分质量 | 无法得知后续流信息, 一些顶点或边会违背贪心策略被分配到负载较小的分区, 从而造成冗余的边割或点割 | 边割 | LGD[ |
贪心地将顶点划分到邻居最多的分区中, 以最小化局部的边割数 |
Fennel[ |
它的思想与LGD非常接近, 但放宽了分区负载的硬约束 | ||||
AKIN[ |
不仅根据邻居数量, 还利用Jaccard相似度作为辅助信息分配顶点, 效率不高 | ||||
文献[ |
在LGD的基础上考虑集群中网络带宽及节点计算能力的不同 | ||||
点割 | Greedy[ |
使用贪心策略, 针对不同类型的边设计不同的划分规则 | |||
HDRF[ |
在Greedy的基础上考虑顶点的度, 优先处理高度顶点 | ||||
混合割 | Ginger[ |
利用类Fennel对低度顶点及其入边划分.利用Hash对高度顶点的入边划分 | |||
基于流的优化划分算法 | 通过提前获取图信息、局部优化或者分布式流的策略, 相比其他方法进一步提高了划分质量 | 由于辅助手段会造成额外的时间或者空间开销, 算法效率相比其他方法要低 | 边割 | 文献[ |
通过基于窗口的策略获取将要分配顶点的局部信息, 以提高划分质量 |
文献[ |
利用上一次划分结果作为全局信息参与这一次的划分 | ||||
Loom[ |
适用于在线查询图的划分需求, 将查询频率高的模式分配到同一分区 | ||||
点割 | Adwise[ |
具体分配策略类似于HDRF, 但它更趋向于将局部的边都聚集在同一分区 | |||
2PS[ |
通过聚类算法提前获取全局信息指导后面的划分 | ||||
RBSEP[ |
在HDRF的基础上, 同时采用了缓存和重分配策略 | ||||
HoVerCut[ |
利用多个线程并行执行多个流式划分算法, 效率较高 | ||||
文献[ |
提出并行的分布式算法, 将问题建模为一个博弈过程 | ||||
混合割 | WASP[ |
对于工作负载自适应, 利用原有的查询信息不断调整分区. 对于拓扑感知, 采用混合切割策略 |
流式图划分算法的特点是将图看成一个顶点或者边序列, 不需要将整个图放到内存中进行划分, 因此它用于划分大规模图数据具有较高的效率. Hash算法是一种简单而有效的方法, 尤其是在降低延迟方面. 在基于邻居分布的算法中, 几乎所有的算法在设计映射函数时除了考虑邻居信息之外, 也将分区负载平衡作为一项考虑其中. LGD和Fennel算法都是顶点划分, 更适用于对不遵循幂律分布的图进行划分. LGD与Fennel类似, 但是Fennel相比较LGD放宽了分区负载的硬约束. AKIN算法在LGD和Fennel的基础上通过考虑顶点之间的相似性, 而不仅仅是单个顶点的邻居分布, 以进一步提高图划分的质量. 但是AKIN算法计算相似性时并没有考虑顶点的度分布, 并且需要一定计算开销. 文献[
动态图的总体规模通常是扩大的, 其中伴随着顶点和边的插入与删除, 且动态图是无界的. 流式图划分算法虽然可以被用于动态图划分, 但具有一定的局限性: 一方面, 流式图划分算法只能处理新顶点或新边, 无法处理图中发生的删除; 另一方面, 流式图划分算法通常不支持对已划分部分的调整, 随着图规模的扩大, 其划分质量较低的弊端将被放大. 针对这些特点, 有一些研究提出了增量式动态图划分算法, 采用不同的策略对不同类型的动态变化进行划分. 这类算法适合于持续增长的动态图. 本节将从单元素增量式划分和批处理增量式划分这两大类分别进行介绍, 并且同样在各个子类中从边割、点割以及混合割不同的划分方式进行归纳总结.
有一些研究为每个单独的动态变化提供了划分策略.
● 边割
文献[
● 点割
GR-DEP[
GR-DEP的分布式动态图划分框架
DynamicDFEP[
DynamicDFEP的框架图
● 混合割
IOGP[
另一些研究则提出了针对一批动态变化的划分策略, 与单元素增量式划分算法相比, 收集一段时间内的动态变化对划分质量的提升更有利, 但牺牲了实时性.
● 边割
文献[
其中,
其中,
● 边割和点割
最近, 文献[
用Δ
DNE是目前效果最好的边划分算法NE的分布式版本, NE通过邻居扩展的策略顺序地生成每个分区, DNE则并行地生成每个分区. 在分区生成过程中, 根据邻居策略选择在分区外邻边最少的顶点
其中,
最终, IncDNE在初始分区的基础上, 用
KGGGP是分布式的顶点划分算法, 它利用边界扩展策略并行地生成每个分区. 它从随机选择的种子顶点
KGGGP的更新函数
增量式图划分算法小结
类型 | 优点 | 缺点 | 划分方式 | 算法 | 特点 |
单元素增量式划分算法 | 具有实时性, 满足时间敏感的图应用的划分需求 | 处理单个动态变化时无法获知其局部动态变化, 可能会影响划分质量 | 边割 | 文献[ |
为插入顶点和边, 删除顶点和边分别提出处理策略, 通过移动单个顶点作局部调整 |
点割 | DynamicDFEP[ |
当顶点或边被删除导致分区负载不平衡时, 用DFEP重划分整个图, 效率不高 | |||
GR-DEP[ |
为插入边和删除边提供处理策略, 通过移动组团边作局部调整 | ||||
混合割 | Leopard[ |
利用Fennel将顶点分配到分区中, 并对局部结构进行调整. 适合于只读图计算任务 | |||
IOGP[ |
先利用Hash分配顶点, 再利用Fennel的思想通过转移顶点优化分区. 对于高度顶点采用点割划分策略. 适用于图的在线查询 | ||||
批处理增量式划分算法 | 由于获知局部动态变化, 利用其信息将进一步提高划分质量 | 缺乏实时性 | 边割 | 文献[ |
将问题表述为线性规划问题利用最优化方法求解, 存在性能瓶颈 |
边割、点割 | 文献[ |
将已有具有迭代特点的静态图划分算法增量化, 对划分质量有一定保障 |
在第1.2节中, 本文介绍了图的动态性主要有两个来源: 图结构的动态性和图计算的动态性. 流式图划分算法和增量式图划分算法主要针对图结构的动态性, 即
当图发生动态变化后, 即顶点或边的插入或删除, 初始图的划分质量会随之下降, 进而影响图计算和图处理的性能, 因此, 一些研究者提出了重划分算法以解决这类问题.
● 边割
在基于边割的图划分环境中, 顶点通常需要被分配到邻居最多的分区. 如
基于边割的重划分
其中,
KL[
有一些研究则针对动态图提出了重划分算法. 文献[
由于多级图划分算法不适合于大规模图, 近期有许多轻量级的重划分算法被提出. 它们只需要少量关于图的信息, 在各个分区中迭代地寻找
基于组的边割重划分
上述方法都假设图划分的环境是同构的且无网络争用, 也就是说各分区之间的单位通信代价都一样. Aragon[
● 点割
在基于点割的图划分环境中, 重划分通过转移边来减少顶点的副本. 如
基于点割的重划分
除此之外, 还有一些基于混合切割的流式图划分方法也使用了重划分思想, 例如: Leopard和IOGP在分配完顶点之后, 对局部结构进行调整, 使分区间的通信代价进一步减少.
在分布式图处理系统中, 图计算大多都是迭代进行的, 在每个超步中, 每个分区都有一部分顶点被激活而进行计算. 但是随着图的遍历, 被激活的顶点的规模会发生动态变化, 例如单源最短路径计算、广度优先搜索、最大匹配算法等. 不同规模的激活顶点会导致分区中计算负载的不均衡, 同时还会导致分区间通信代价与边割或点割数量不一致, 从而导致原始划分不契合图计算模型. 为了提升图计算的效率, 需要在图计算中进行动态重划分.
● 边割
GPS[
图计算的动态性导致的计算性能下降体现在很多方面, 通常, 重划分算法需要首先检测性能下降的来源, 再针对性地通过顶点或边的转移来提升性能. 在基于边割的图划分环境中, Mizan[
CatchW[
● 点割
在基于点割的图划分环境中, GrapH[
图重划分算法小结
类型 | 优点 | 缺点 | 划分方式 | 算法 | 特点 |
针对结构动态的划分算法 | 处理图结构的动态变化, 提高图划分的质量 | 由于顶点或边的迁移, 会造成额外的时间和空间开销 | 边割 | 文献[ |
多级图的重划分算法, 适合较小规模的图划分 |
xdgp[ |
利用标签传播, 将顶点转移到邻居多的分区作局部调整 | ||||
Hermes[ |
通过移动多个增益最大的顶点优化分区, 更适合于分布式图数据库 | ||||
文献[ |
解决Hermes的移动干扰问题, 通过移动组团点优化分区, 具有较高的划分质量 | ||||
Aragon[ |
考虑异构环境, 每次选择两个分区进行顶点的转移优化分区 | ||||
Paragon[ |
考虑异构环境, 选择一个主分区, 通过主分区将剩下的分区分组, 各组并行运行Aragon | ||||
Planar[ |
考虑异构环境, 每个分区各自寻找增益大于0的顶点, 在配额的范围内转移顶点优化分区 | ||||
点割 | 文献[ |
通过移动组团边优化分区进一步改进划分质量, 算法效率较高 | |||
针对计算动态的划分算法 | 能够使得特定图计算应用迭代过程中负载更平衡, 通信代价更低 | 顶点或者边的重分配会造成额外的开销 | 边割 | GPS[ |
每个分区都维护包含潜在待重分配顶点的一个集合, 在分区负载不变的前提下交换集合中的顶点优化分区 |
Mizan[ |
考虑平衡分区负载, 首先识别不平衡来源, 然后确定顶点转移的目标, 最后从高负载分区转移顶点到低负载分区 | ||||
CatchW[ |
在平衡分区负载的同时, 寻找可以减少通信代价的顶点, 尝试减少分区间的边割 | ||||
LogGP[ |
利用运行统计信息或历史分区日志来进行重划分优化分区 | ||||
点割 | GrapH[ |
通过转移一组边, 减少分区间的通信量, 以提高划分质量 | |||
GraphSteal[ |
适合于平衡各分区出现的运行时间不平衡, 将边从较慢的分区转移到较快的分区 |
动态图重划分算法分为针对图结构动态的重划分算法和针对图计算动态的重划分算法.
● 在针对图结构动态的重划分算法中, 文献[
● 在针对图计算动态的重划分算法中, 重点是要根据不同的图计算任务灵活处理, 这些算法主要适用于那些较高的负载平衡和较低的通信代价带来的收益远远大于顶点或边的重分配造成额外开销的图划分任务.
由于性能开销的影响, 图的动态性导致的划分质量下降的问题是传统静态图划分算法无法解决的, 因此, 近期有一些工作针对动态图划分问题进行了研究. 本节首先总结分析了不同类别的动态图划分算法的特点, 之后讨论了动态图划分问题存在的挑战, 并对未来的研究方向加以展望.
本文将动态图划分算法分为流式图划分算法、增量式图划分算法和图重划分算法这三大类, 详细的分类汇总可见
动态图划分算法总结
类型 | 子类 | 划分方式 | 特点 |
流式图划分算法 | 基于哈希的划分算法 | 边割[ |
使用一致的哈希函数将顶点或边映射到不同的分区中. 效率高, 具有较低的延迟, 但划分质量低 |
基于邻居分布的划分算法 | 边割[ |
利用新到达的顶点和边的邻居信息, 在映射函数中既考虑顶点和边的连接情况, 也考虑分区负载大小. 划分质量较高 | |
基于流的优化划分算法 | 边割[ |
利用提前获取图信息、局部优化和分布式流这3种策略解决无法得知后续流信息的单元素流算法(哈希或者邻居分布)存在的弊端. 划分质量高, 但效率较低 | |
增量式图划分算法 | 单元素增量式划分算法 | 边割[ |
为每个单独的动态变化(单个顶点或边的插入或删除)提供划分策略. 实时处理持续增长图, 具有较好的划分质量, 较低开销 |
批处理增量式划分算法 | 边割[ |
针对一批动态变化的划分策略, 能够保证一定的划分质量, 但是不具有实时性, 有一些算法不能够处理大规模图且开销大 | |
图重划分算法 | 针对结构动态的划分算法 | 边割[ |
专注于在图结构发生动态变化后对分区进行优化, 通过分区间顶点或边的转移来提高图划分的质量 |
针对计算动态的划分算法 | 边割[ |
专注于在真实的图计算应用中, 被激活的顶点的规模发生动态变化后通过顶点或边的转移对分区进行优化 |
流式图划分算法支持动态地向分区中添加顶点和边, 可以处理动态图中拓扑结构的变化. 最近的一些关于流式图划分的研究逐渐跳出单元素流和分区结构无法调整的设定, 获得了比较好的效果. 但是流式动态图划分算法只能处理顶点和边的插入, 而不能很好地处理顶点和边的删除. 一些研究者提出了增量式图划分算法, 分为单元素增量式图划分和批量增量式图划分: 单元素增量式图划分的研究很多都采用了重分配的思想; 批量增量式图划分研究中, 一个很重要的工作是利用已有的静态图划分算法得到动态图划分算法. 图的重划分算法分为针对图结构动态的算法和针对图计算动态的算法. 图的重划分是提升划分质量的主要手段, 大部分动态图划分算法的研究都采用了重划分的思想, 通过迭代进行顶点或边的转移, 逐渐减少分区间的交互量.
基于流的方法是加载图的一种很好的选择, 因为它们不需要将整个图放在内存中进行划分. 顶点或边流可以同时在管道中加载和划分. 因此, 一些分布式图处理系统将流方法作为默认的划分方法. 此外, 流式图划分算法中的基于哈希和基于邻居分布的算法由于具有较高的效率, 一般用于图的初始划分. 增量式动态图划分算法中的单元素增量式算法适合用于实时场景中, 能够获得更好的划分质量和性能. 针对结构动态的重划分算法能够处理由图发生动态变化而导致的划分质量下降的问题, 拥有较好的划分质量. 而针对计算动态的重划分算法能够切实考虑到真实的图计算和处理的运行过程. 在迭代计算中, 针对不同的图计算任务的特点, 通过顶点或者边的转移不断提高分布式图处理的性能.
本文对动态图划分算法进行了分析、总结和归纳. 动态图划分虽然已经有了比较深入的研究, 取得了一定的成果, 但仍面临不少困难和挑战, 主要如下.
1) 基于边割的动态图划分已经有较为完善的研究. 大量的研究证明: 基于点割的图划分在处理具有幂律分布特点的真实图方面具有更好的效果, 而对基于点割的动态图划分的研究还并不多, 尤其是基于点割的图重划分算法, 其中的难点在于如何找到能够减少交互量的边进行转移;
2) 大多数图重划分算法并不关心图是如何发生动态变化的, 实际上, 它们只是对动态图的一个快照通过局部调整进行优化, 比较适合离线场景. 然而, 真实图是实时动态变化的, 如何在满足实时性的条件下获得高质量的划分结果, 是动态图划分的一大挑战;
3) 对于具有幂律分布特点的真实图, 研究表明: 基于边割的划分有着更好的局部性, 而基于点割的划分有着更好的负载平衡. 混合割结合了边割和点割的优势. 然而, 现有的工作对混合割的研究较少, 仅仅在流式图划分算法和增量式图划分算法中有少量的工作. 因此, 研究高性能的基于混合割的动态图划分方法是一大挑战;
4) 目前, 大多数图划分算法都是基于简单图, 而从真实世界中抽象出来的图是复杂的, 比如有向图、带权图、数据流图、概率图、复杂网络、超图以及知识图谱等. 如何设计合理的图划分算法处理特殊图也是一大挑战;
5) 在如今的大数据时代, 从真实应用中抽象出来的图数据是超大规模和动态变化的. 集中式环境下的图划分算法已经难以适应当前应用的需求, 分布式并行环境下的图划分算法的研究日益迫切;
6) 目前的研究大多都以最小化分区间的交互量和平衡分区负载为目标, 而现实的图处理场景非常复杂. 由于计算环境的异构性、图计算的动态性等原因, 最小化交互量和平衡分区负载并不等同于最大化图计算的性能. 图划分的最终目的是提升图计算的性能, 因此, 如何将图划分与真实的分布式图处理结合是一大挑战.
综上所述, 从当前的研究现状来看, 动态图划分问题的研究还有继续开展的空间. 随着数据规模的快速扩张, 如何在实时场景中以分布式的方式处理动态图的划分, 将会是研究的一个主要方向. 如何考虑计算结构异构性和计算动态性, 更好地结合图划分和真实的大规模分布式图处理, 以及针对一些特殊图设计动态图划分方法等, 是研究的一大重点. 除此之外, 基于混合割的图划分由于它在真实图上的划分效果更好, 也将逐渐成为研究的主流. 未来的研究方向主要包括以下几个方面.
1) 基于点割的动态图重划分算法的研究. 现有的动态重划分方法大多基于边割, 然而, 许多分布式框架使用点割模型. 因此, 研究高性能的基于点割的动态图重划分算法, 是未来的一大研究方向. 此外, 现有的动态重划分方法是针对同步系统的. 在异步系统中, 顶点或边的迁移更为复杂, 这需要锁等并发控制机制来避免不一致. 如何设计异步的动态重划分方法, 也是未来的一个研究方向.
2) 基于混合割的动态图划分算法的研究. 基于混合割的划分策略能够结合边割和点割各自的优势. 对于具有幂律分布特点的真实图, 基于混合割的划分方法实现了更好的分区负载平衡和最小化分区间的通信量. 因此, 研究高性能的基于混合割的动态图划分算法, 将会是未来的一大研究方向.
3) 实时动态图划分算法的研究. 已有的大量工作都是对动态图的一个快照进行分析, 并没有提出实时处理动态变化的策略. 而如今, 有一些图应用需要实时处理动态变化图, 以满足高性能的分布式图处理任务. 因此, 如何研究单元素增量式动态图划分算法, 能够满足实时性并获得高质量划分结果, 将是未来的一个研究方向.
4) 针对特殊图的动态图划分算法的研究. 从真实应用中抽象出来的图数据结构是千变万化的, 如有向图、带权图等. 此外, 还有一些富有特殊含义的图, 如数据流图、概率图、复杂网络等. 如何研究出针对这些特殊图的分布式并行环境下的动态图划分算法, 也是未来的一个研究方向.
5) 针对知识图谱和超图的动态图划分算法的研究. 超图是图的一种扩展形式, 其中一条边(通常称为超边或网)可以连接任意数量的顶点. 知识图谱也是图的某种扩展形式, 其在顶点和边上往往会附加更多的属性信息, 用于描述现实世界中事物的广泛联系. 虽然已有一些工作针对知识图谱和超图提出了划分算法, 但大多是基于静态图的. 因此, 研究高性能的动态图划分算法划分超大规模知识图谱和超图, 是未来的一大研究方向.
6) 针对硬件异构性的动态图划分算法的研究. 在真实的分布式图处理中, 处于不同地理位置的机器的硬件资源存在异构性, 如CPU、GPU、存储容量等, 并且不同机器间通信时的网络带宽和网络价格不一致. 因此, 如何设计针对计算异构性的动态图划分算法, 也是未来的一大研究方向.
7) 针对图计算动态性的动态图划分算法的研究. 对于不同的分布式图处理任务, 有着不同的通信和计算模式, 故即使是以最小化分区间的交互量和平衡分区负载为目标的最优的图划分方法, 也不能保证所有图计算任务的性能. 这就需要考虑图计算运行时特性, 更好地将图划分与真实的大规模分布式图处理相结合. 因此, 如何利用机器学习、深度学习、图论、统计学等技术设计任务驱动的动态图划分算法, 将会是未来的一大研究方向.
http://snap.stanford.edu/data/index.html]]>
http://konect.cc/networks/]]>
http://networkrepository.com/networks.php]]>
http://law.di.unimi.it/datasets.php]]>
Leskovec J, Dumais S, Horvitz E. Web projections: Learning from contextual subgraphs of the Web. In: Proc. of the 16th Int'l Conf. on World Wide Web (WWW). ACM, 2007. 471-480.
Chakrabarti D, Zhan Y, Faloutsos C. R-MAT: A recursive model for graph mining. In: Proc. of the 4th SIAM Int'l Conf. on Data Mining (SDM). 2004. 442-446.
Leskovec J, Chakrabarti D, Kleinberg JM, Faloutsos C, Ghahramani Z. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 2010, 11(Feb. ): 985-1042.
Malewicz G, Austern MH, Bik AJ, Dehnert J, Horn I, Leiser N, Czajkowski G. Pregel: A system for large-scale graph processing. In: Proc. of the 2010 Int'l Conf. on Management of Data (SIGMOD). 2010. 135-146.
https://giraph.apache.org/]]>
Low Y, Bickson D, Gonzalez J, Guestrin C, Kyrola A, Hellerstein JM. Distributed GraphLab: A framework for machine learning and data mining in the cloud. Proc. of the VLDB Endowment, 2012, 5(8): 716-727.
Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C. Powergraph: Distributed graph-parallel computation on natural graphs. In: Proc. of the 10th USENIX Symp. on Operating Systems Design and Implementation (OSDI). 2012. 17-30.
Chen R, Shi J, Chen Y, Zang B, Guan H, Chen H. Powerlyra: Differentiated graph computation and partitioning on skewed graphs. ACM Trans. on Parallel Computing (TOPC), 2018, 5(3): 13: 1-13: 39.
Gonzalez JE, Xin RS, Dave A, Crankshaw D, Franklin MJ, Stoica I. Graphx: Graph processing in a distributed dataflow framework. In: Proc. of the 11th USENIX Symp. on Operating Systems Design and Implementation (OSDI). 2014. 599-613.
Li D, Zhang Y, Wang J, Tan K. TopoX: Topology refactorization for efficient graph partitioning and processing. Proc. of the VLDB Endowment, 2019, 12(8): 891-905.
Cui PJ. Yuan Y, Li CH, Zhang C, Wang RG. RGraph: An effective distributed graph processing system based on RDMA. Ruan Jian Xue Bao/Journal of Software, 2022, 33(3): 1018-1042 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6449.htm[doi: 10.13328/j.cnki.jos.006449]
崔鹏杰, 袁野, 李岑浩, 张灿, 王国仁. RGraph: 基于RDMA的高效分布式大图数据处理系统. 软件学报, 2022, 33(3): 1018-1042. http://www.jos.org.cn/1000-9825/6449.htm[doi: 10.13328/j.cnki.jos.006449]
Donath WE, Hoffman AJ. Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 1972, 15(3): 938-944.
Donath WE, Hoffman AJ. Lower bounds for the partitioning of graphs. IBM Journal of Research and Development, 1973, 17(5): 420-425.
Simon HD. Partitioning of unstructured problems for parallel processing. Computer Systems Science and Engineering, 1991, 2(2): 135-148.
Williams RD. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Concurrency and Computation: Practice and Experience, 1991, 3(5): 457-481.
Karypis G. METIS: Unstructured graph partitioning and sparse matrix ordering system. Technical Report, 1997.
Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998, 20(1): 359-392.
Karypis G, Kumar V. Multilevel graph partitioning schemes. In: Proc. of the 1995 Int'l Conf. on Parallel Processing (ICPP). 1995. 113-122.
Xie C, Yan L, Li WJ, Zhang Z. Distributed power-law graph computing: Theoretical and empirical analysis. In: Advances in Neural Information Processing Systems (NIPS). 2014. 1673-1681.
Jain N, Liao G, Willke TL. Graphbuilder: Scalable graph ETL framework. In: Proc. of the 1st Int'l Workshop on Graph Data Management Experiences and Systems. ACM, 2013.
Hanai M, Suzumura T, Tan WJ, Liu ES, Theodoropoulos G, Cai W. Distributed edge partitioning for trillion-edge graphs. Proc. of the VLDB Endowment, 2019, 12(13): 2379-2392.
Fan W, Liu M, Tian C, Xu R, Zhou J. Incrementalization of graph partitioning algorithms. Proc. of the VLDB Endowment, 2020, 13(8): 1261-1274.
Stanton I, Kliot G. Streaming graph partitioning for large distributed graphs. In: Proc. of the 18th Int'l Conf. on Knowledge Discovery and Data Mining (SIGKDD). ACM, 2012. 1222-1230.
Tsourakakis CE, Gkantsidis C, Radunovic B, Vojnovic M. Fennel: Streaming graph partitioning for massive scale graphs. In: Proc. of the 7th ACM Int'l Conf. on Web Search and Data Mining (WSDM). ACM, 2014. 333-342.
Zhang W, Chen Y, Dai D. AKIN: A streaming graph partitioning algorithm for distributed graph storage systems. In: Proc. of the 18th IEEE/ACM Int'l Symp. on Cluster, Cloud and Grid Computing. IEEE, 2018. 183-192.
Patwary MAK, Garg S, Kang B. Window-based streaming graph partitioning algorithm. In: Proc. of the Australasian Computer Science Week Multiconference. ACM, 2019. 1-10.
Firth H, Missier P, Aiston J. Loom: Query-aware partitioning of online graphs. In: Proc. of the 21st Int'l Conf. on Extending Database Technology (EDBT). 2018. 337-348.
Petroni F, Querzoni L, Daudjee K, Kamali S, Iacoboni G. Hdrf: Stream-based partitioning for power-law graphs. In: Proc. of the 24th Int'l Conf. on Information and Knowledge Management (CIKM). ACM, 2015. 243-252.
Mayer C, Mayer R, Tariq MA, Geppert H, Laich L, Rieger L, Rothermel K. Adwise: Adaptive window-based streaming edge partitioning for high-speed graph processing. In: Proc. of the 38th Int'l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2018. 685-695.
Sajjad HP, Payberah AH, Rahimian F, Vlassov V, Haridi S. Boosting vertex-cut partitioning for streaming graphs. In: Proc. of the 2016 IEEE Int'l Congress on Big Data (BigData Congress). IEEE, 2016. 1-8.
Nicoara D, Kamali S, Daudjee K, Chen L. Hermes: Dynamic partitioning for distributed social network graph databases. In: Proc. of the 18th Int'l Conf. on Extending Database Technology (EDBT). 2015. 25-36.
Mayer C, Tariq MA, Mayer R, Rothermel K. Graph: Traffic-aware graph processing. IEEE Trans. on Parallel and Distributed Systems, 2018, 29(6): 1289-1302.
Xu N, Chen L, Cui B. LogGP: A log-based dynamic graph partitioning method. Proc. of the VLDB Endowment, 2014, 7(14): 1917-1928.
Gill G, Dathathri R, Hoang L, Pingali K. A study of partitioning policies for graph analytics on large-scale distributed platforms. Proc. of the VLDB Endowment, 2018, 12(4): 321-334.
Adoni HWY, Nahhal T, Krichen M, Aghezzaf B, Elbyed A. A survey of current challenges in partitioning and processing of graph-structured data in parallel and distributed systems. Distributed and Parallel Databases, 2020, 38(2): 495-530.
Pacaci A, Özsu MT. Experimental analysis of streaming algorithms for graph partitioning. In: Proc. of the 2019 Int'l Conf. on Management of Data (SIGMOD). ACM, 2019. 1375-1392.
Abbas Z, Kalavri V, Carbone P, Vlassov V. Streaming graph partitioning: An experimental study. Proc. of the VLDB Endowment, 2018, 11(11): 1590-1603.
Verma S, Leslie LM, Shin Y, Gupta I. An experimental comparison of partitioning strategies in distributed graph processing. Proc. of the VLDB Endowment, 2017, 10(5): 493-504.
Soudani NM, Fatemi A, Nematbakhsh M. An investigation of big graph partitioning methods for distribution of graphs in vertex-centric systems. Distributed and Parallel Databases, 2020, 38(1): 1-29.
Xu JF, Dong YH, Wang SY, He XM, Chen HH. A review of algorithms for partitioning large-scale graph data. Dian Xin Ke Xue/Telecommunications Science, 2014, 30(7): 100-106 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-0801.2014.07.016]
许金凤, 董一鸿, 王诗懿, 何贤芒, 陈华辉. 大规模图数据划分算法综述. 电信科学, 2014, 30(7): 100-106. [doi: 10.3969/j.issn.1000-0801.2014.07.016]
Karypis G, Aggarwal R, Kumar V, Shekhar S. Multilevel hypergraph partitioning: Applications in VLSI domain. IEEE Trans. on Very Large Scale Integration (VLSI) Systems, 1999, 7(1): 69-79.
Alpert CL, Hagen LW, Kahng AB. A hybrid multilevel/genetic approach for circuit partitioning. In: Proc. of the Asia Pacific Conf. on Circuits and Systems (APCCAS'96). IEEE, 1996.
Zhang E, Gao L. A circuit partition algorithm based on point cut. Chinese Journal of Computers, 2014, 37(7): 1528-1537 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2014.01528]
张恩利, 高琳. 一种基于点割的电路划分算法. 计算机学报, 2014, 37(7): 1528-1537. [doi: 10.3724/SP.J.1016.2014.01528]
Pellegrini F, Roman J. Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In: Proc. of the High-Performance Computing and Networking. Springer-Verlag, 1996. 493-498.
Hendrickson B, Leland RW. A multi-level algorithm for partitioning graphs. In: Proc. of the SC'95 Conf. ACM, 1995.
Deng L, Dai N, Xu B, Xing C, Chen M. PNFVNbM: A method to partition large-scale NFV networks based on Metis. Chinese Journal of Computers, 2020, 43(10): 1958-1968 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2020.01958]
邓理, 戴宁赟, 许博, 邢长友, 陈鸣. PNFVNbM: 一种基于Metis划分大规模NFV网络的方法. 计算机学报, 2020, 43(10): 1958-1968. [doi: 10.11897/SP.J.1016.2020.01958]
Karypis G, Kumar V. Parallel multilevel series
Chevalier C, Pellegrini F. PT-scotch: A tool for efficient parallel graph ordering. Parallel Computing, 2008, 34(6-8): 318-331.
Rahimian F, Payberah AH, Girdzijauskas S, Jelasity M, Haridi S. Ja-be-Ja: A distributed algorithm for balanced graph partitioning. In: Proc. of the 7th Int'l Conf. on Self-adaptive and Self-Organizing Systems (SASO). IEEE, 2013. 51-60.
http://glaros.dtc.umn.edu/gkhome/views/metis]]>
Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49(2): 291-307.
Fiduccia CM, Mattheyses RM. A linear-time heuristic for improving network partitions. In: Proc. of the 19th Design Automation Conf. (DAC). IEEE, 1982. 175-181.
LaSalle D, Karypis G. A parallel hill-climbing refinement algorithm for graph partitioning. In: Proc. of the 45th Int'l Conf. on Parallel Processing (ICPP). IEEE, 2016. 236-241.
Xu JF, Dong YH, Wang SY, He XM, Chen HH. LGP-SA: Large-scale graph partitioning algorithm based on simulated annealing in distributed environment. Dian Xin Ke Xue/Telecommunications Science, 2016, 32(2): 83-91 (in Chinese with English abstract). [doi: 10.11959/j.issn.1000-0801.2016078]
许金凤, 董一鸿, 王诗懿, 何贤芒, 陈华辉. LGP-SA: 分布式环境下基于模拟退火的大规模图划分算法. 电信科学, 2016, 32(2): 83-91. [doi: 10.11959/j.issn.1000-0801.2016078]
Wang L, Xiao Y, Shao B, Wang H. How to partition a billion-node graph. In: Proc. of the 30th Int'l Conf. on Data Engineering (ICDE). IEEE, 2014. 568-579.
Martella C, Logothetis D, Loukas A, Siganos G. Spinner: Scalable graph partitioning in the cloud. In: Proc. of the 33rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2017. 1083-1094.
Yan J, Tan G, Sun N. Study on partitioning real-world directed graphs of skewed degree distribution. In: Proc. of the 44th Int'l Conf. on Parallel Processing (ICPP). IEEE, 2015. 699-708.
Zheng A, Labrinidis A, Faloutsos C. Skew-resistant graph partitioning. In: Proc. of the 33rd Int'l Conf. on Data Engineering (ICDE). IEEE, 2017. 151-154.
Kim M, Candan KS. SBV-cut: Vertex-cut based graph partitioning using structural balance vertices. Data & Knowledge Engineering, 2012, 72: 285-303.
Rahimian F, Payberah AH, Girdzijauskas S, Haridi S. Distributed vertex-cut partitioning. In: Proc. of the Distributed Applications and Interoperable Systems (DAIS). Springer, 2014. 186-200.
Zhang C, Wei F, Liu Q, Tang ZG, Li Z. Graph edge partitioning via neighborhood heuristic. In: Proc. of the 23rd Int'l Conf. on Knowledge Discovery and Data Mining (SIGKDD). ACM, 2017. 605-614.
Ji S, Bu C, Li L, Wu X. Local graph edge partitioning with a two-stage heuristic method. In: Proc. of the 39th IEEE Int'l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2019. 228-237.
Zhang Y, Liu Y, Yu J, Liu P, Guo L. Vsep: A distributed algorithm for graph edge partitioning. In: Proc. of the Int'l Conf. on Algorithms and Architectures for Parallel Processing. Springer, 2015. 71-84.
Li Y, Constantin C, Mouza C. SGVcut: A vertex-cut partitioning tool for random walks-based computations over social network graphs. In: Proc. of the 29th Int'l Conf. on Scientific and Statistical Database Management. ACM, 2017.
Margo D, Seltzer M. A scalable distributed graph partitioner. Proc. of the VLDB Endowment, 2015, 8(12): 1478-1489.
Guerrieri A, Montresor A. DFEP: Distributed funding-based edge partitioning. In: Proc. of the European Conf. on Parallel Processing. Springer, 2015. 346-358.
Li D, Zhang Y, Wang J, Tan KL. TopoX: Topology refactorization for efficient graph partitioning and processing. Proc. of the VLDB Endowment, 2019, 12(8): 891-905.
Zhu X, Chen W, Zheng W, Ma X. Gemini: A computation-centric distributed graph processing system. In: Proc. of the OSDI 2016. USENIX Association, 2016. 301-316.
Avdiukhin D, Pupyrev S, Yaroslavtsev G. Multi-dimensional balanced graph partitioning via projected gradient descent. Proc. of the VLDB Endowment, 2019, 12(8): 906-919.
Fan W, Jin R, Liu M, Lu P, Luo X, Xu R, Yin Q, Yu W, Zhou J. Application driven graph partitioning. In: Proc. of the SIGMOD. ACM, 2020. 1765-1779.
Wang Z, Gu Y, Bao Y, Yu G. OnFlyP: Distributed online large graph partitioning algorithm based on directional edge switching. Chinese Journal of Computers, 2015, 38(9): 1838-1851 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2015.01838]
王志刚, 谷峪, 鲍玉斌, 于戈. OnFlyP: 基于定向边交换的分布式在线大图划分算法. 计算机学报, 2015, 38(9): 1838-1851. [doi: 10.11897/SP.J.1016.2015.01838]
Wang X, Chen W, Yang Y, Zhang X, Feng Z. A review of knowledge graph partitioning algorithms. Chinese Journal of Computers, 2021, 44(1): 235-260 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2021.00235]
王鑫, 陈蔚雪, 杨雅君, 张小旺, 冯志勇. 知识图谱划分算法研究综述. 计算机学报, 2021, 44(1): 235-260. [doi: 10.11897/SP.J.1016.2021.00235]
Gottesbüren L, Heuer T, Sanders P, Schlag S. Scalable shared-memory hypergraph partitioning. In: Proc. of the Workshop on Algorithm Engineering and Experiments (ALENEX). 2021. 16-30.
Papa DA, Markov I. Hypergraph partitioning and clustering. In: Handbook of Approximation Algorithms and Metaheuristics. 2007.
LI Q, LI H, Zhong J, Ying CT, LI Q. Research on graph partitioning in heterogeneous computing environment. Chinese Journal of Computers, 2021, 44(8): 1751-1766 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2021.01751]
李琪, 李虎雄, 钟将, 英昌甜, 李青. 异构计算环境中图划分算法的研究. 计算机学报, 2021, 44(8): 1751-1766. [doi: 10.11897/SP.J.1016.2021.01751]
Nishimura J, Ugander J. Restreaming graph partitioning: Simple versatile algorithms for advanced balancing. In: Proc. of the 19th Int'l Conf. on Knowledge Discovery and Data Mining (SIGKDD). ACM, 2013. 1106-1114.
Mayer R, Orujzade K, Jacobsen HA. 2PS: High-quality edge partitioning with two-phase streaming. arXiv: 2001. 07086, 2020.
Taimouri M, Saadatfar H. RBSEP: A reassignment and buffer based streaming edge partitioning approach. Journal of Big Data, 2019, 6(1): 1-17.
Hua QS, Li Y, Yu D, Jin H. Quasi-streaming graph partitioning: A game theoretical approach. IEEE Trans. on Parallel and Distributed Systems, 2019, 30(7): 1643-1656.
Davoudian A, Chen L, Tu H, Liu M. A workload-adaptive streaming partitioner for distributed graph stores. Data Science and Engineering, 2021, 6(2): 163-179.
Abdolrashidi A, Ramaswamy L. Continual and cost-effective partitioning of dynamic graphs for optimizing big graph processing systems. In: Proc. of the 2016 IEEE Int'l Congress on Big Data (BigData Congress). IEEE, 2016. 18-25.
Li H, Yuan H, Huang J, Cui J, Ma X, Wang S, Yoo J, Yu PS. Group reassignment for dynamic edge partitioning. IEEE Trans. on Parallel and Distributed Systems, 2021, 32(10): 2477-2490.
Sakouhi C, Aridhi S, Guerrieri A, Sassi S, Montresor A. Dynamicdfep: A distributed edge partitioning approach for large dynamic graphs. In: Proc. of the 20th Int'l Database Engineering & Applications Symposium (IDEAS). ACM, 2016. 142-147.
Dai D, Zhang W, Chen Y. IOGP: An incremental online graph partitioning algorithm for distributed graph databases. In: Proc. of the 26th Int'l Symp. on High-performance Parallel and Distributed Computing. ACM, 2017. 219-230.
Huang J, Abadi DJ. Leopard: Lightweight edge-oriented partitioning and replication for dynamic graphs. Proc. of the VLDB Endowment, 2016, 9(7): 540-551.
Ou CW, Ranka S. Parallel incremental graph partitioning using linear programming. In: Proc. of the 1994 Conf. on Supercomputing. IEEE, 1994. 458-467.
Schloegel K, Karypis G, Kumar V. Dynamic repartitioning of adaptively refined meshes. In: Proc. of the 1998 ACM/IEEE Conf. on Supercomputing. ACM, 1998.
Vaquero LM, Cuadrado F, Logothetis D, Martella C. Adaptive partitioning for large-scale dynamic graphs. In: Proc. of the 34th Int'l Conf. on Distributed Computing Systems (ICDCS). IEEE, 2014. 144-153.
https://neo4j.com/]]>
Li H, Yuan H, Huang J, Cui J, Yoo J. Dynamic graph repartitioning: From single vertex to vertex group. In: Proc. of the 25th Int'l Conf. on Database Systems for Advanced Applications (DASFAA). Springer, 2020. 482-497.
Zheng A, Labrinidis A, Chrysanthis PK. Architecture-aware graph repartitioning for data-intensive scientific computing. In: Proc. of the 2014 IEEE Int'l Conf. on Big Data (Big Data). IEEE, 2014. 78-85.
Zheng A, Labrinidis A, Pisciuneri PH, Chrysanthis PK, Givi P. PARAGON: Parallel architecture-aware graph partition refinement algorithm. In: Proc. of the 19th Int'l Conf. on Extending Database Technology (EDBT). 2016. 365-376.
Zheng A, Labrinidis A, Chrysanthis PK. Planar: Parallel lightweight architecture-aware adaptive graph repartitioning. In: Proc. of the 32nd Int'l Conf. on Data Engineering (ICDE). IEEE, 2016. 121-132.
Li H, Yuan H, Huang J. Real-time edge repartitioning for dynamic graph. In: Proc. of the 28th ACM Int'l Conf. on Information and Knowledge Management (CIKM). ACM, 2019. 2125-2128.
Salihoglu S, Widom J. GPS: A graph processing system. In: Proc. of the Scientific and Statistical Database Management (SSDBM). 2013. 1-12.
Khayyat Z, Awara K, Alonazi A, Jamjoom H, Williams D, Kalnis P. Mizan: A system for dynamic load balancing in large-scale graph processing. In: Proc. of the 8th European Conf. on Computer Systems (EuroSys). ACM, 2013. 169-182.
Shang Z, Yu JX. Catch the wind: Graph workload balancing on cloud. In: Proc. of the 29th Int'l Conf. on Data Engineering (ICDE). IEEE, 2013. 553-564.
Kumar D, Raj A, Dharanipragada J. GraphSteal: Dynamic re-partitioning for efficient graph processing in heterogeneous clusters. In: Proc. of the 10th Int'l Conf. on Cloud Computing (CLOUD). IEEE, 2017, 439-446.