分布式图计算论文 (图分割)

刚把手头的论文投出去。第三个工作暂时想往分布式方向上做。简单做了个调研,把相关的一些论文做了一个整理。这个系列第一部分主要整理图分割相关论文。

  1. Dynamic Scaling for Parallel Graph Computations (VLDB 2019)

    这篇文章主要探讨的是当集群中增加/减少了k个节点后,图数据需要重新分区。在这个过程中,如何使各个节点之间保持负载均衡,同时使得复制因子(replication factor,直观理解就是点分割的方式下,点在所有节点重叠的数量)与迁移代价(migration cost,数据从一个节点迁移到另外一个节点的数量)尽量的小。
    

    使用的平台 Grape
    论文链接 link

  2. A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms (VLDB 2018)

    这篇文章是综述类型的文章,对于不同的图算法,衡量了不同图分割策略的性能差异。同时,这篇文章提出了预测通讯代价的分割策略,基于此可以帮助预估和理解在通讯中的性能差异。最后,这篇文章给出了利用决策树运行时给出分割策略的算法。
    

    $\rightarrow$ 使用的平台 Galois
    $\rightarrow$ 通讯优化 Gluon

    论文链接 link

  3. Experimental Analysis of Distributed Graph Systems (VLDB 2018)

    这篇文章主要系统的分析了8个平行图计算系统:Hadoop, HaLoop, Vertica, Giraph, GraphLab (PowerGraph), Blogel, Flink Gelly, 以及GraphX (SPARK)。使用了四个数据集:Twitter, World Road Network, UK 200705, 以及ClueWeb。包含了四个测评算法:(PageRank, WCC, SSSP 和 K-hop)。
    

    论文链接 link
    特点罗列如下(截图自原文):

  4. Experimental Analysis of Streaming Algorithms for Graph Partitioning (SIGMOD 19)

    这篇文章也是综述类型的文章。主要研究了图分割算法对系统性能、资源利用和可扩展性的影响。实验结果没有图分割策略在所有的图算法当中都有最好的性能。
    

    论文链接 link
    图分割算法的特性罗列如下(截图自原文):

  5. A Scalable Distributed Graph Partitioner (VLDB 15) 论文链接 link

  6. An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing (VLDB 16) 论文链接 link

小结:

  1. 没有图分割适用于所有应用场景。
  2. 图分割策略依赖于图分布、图算法以及集群规模。