Page 260 - 《软件学报》2024年第4期

1838 软件学报 2024 年第 35 卷第 4 期

5 总 结

本文提出了基于顶点组重分配的动态增量图划分算法 ED-IDGP 来解决现实中持续增长的动态图划分问题,
设计了处理实时动态图中顶点插入、边插入、顶点删除和边删除这 4 种不同的动态变化类型的动态处理器, 并在
每次处理完单元更新后通过在分区发生动态变化的附近执行提出的局部优化器进一步提高图划分的质量. 本文在
真实数据集上将 ED-IDGP 算法与现有的先进动态图划分算法从不同的维度和不同的度量指标进行了充分的对
比. 实验结果表明, ED-IDGP 算法的标准化边切割、边切割改进值和负载平衡改进值分别平均比现有的动态图划
分算法低 27.81%、26.34% 和 24.04%. 本文还将各个算法获得的动态图划分结果导入到分布式图处理系统 Giraph
中, 通过运行分布式图计算任务评估了 ED-IDGP 算法的性能. ED-IDGP 算法的执行时间和通信成本分别平均比
现有的动态图划分算法低 20.96% 和 27.44%.

References:
[1] Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski G. Pregel: A system for large-scale graph processing. In:
Proc. of the 2010 ACM SIGMOD Int’l Conf. on Management of Data. Indianapolis: ACM, 2010. 135–146. [doi: 10.1145/1807167.
1807184]
[2] Giraph. 2021. https://giraph.apache.org/
[3] 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. [doi: 10.14778/2212351.2212354]
[4] Chen R, Shi JX, Chen YZ, Zang BY, Guan HB, Chen HB. PowerLyra: Differentiated graph computation and partitioning on skewed
graphs. ACM Trans. on Parallel Computing, 2018, 5(3): 13. [doi: 10.1145/3298989]
[5] Cui PJ, Yuan Y, Li CH, Zhang C, Wang GR. RGraph: Effective distributed graph data 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]
[6] Neo4j. 2022. https://neo4j.com/
[7] Sarwat M, Elnikety S, He YX, Kliot G. Horton: Online query execution engine for large distributed graphs. In: Proc. of the 28th IEEE Int’l
Conf. on Data Engineering. Arlington: IEEE, 2012. 1289–1292. [doi: 10.1109/ICDE.2012.129]
[8] Kang U, Tong HH, Sun JM, Lin CY, Faloutsos C. Gbase: A scalable and general graph management system. In: Proc. of the 17th ACM
SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. San Diego: Association for Computing Machinery, 2011. 1091–1099.
[doi: 10.1145/2020408.2020580]
[9] Andreev K, Racke H. Balanced graph partitioning. Theory of Computing Systems, 2006, 39(6): 929–939. [doi: 10.1007/s00224-006-1350-7]
[10] Hendrickson B, Leland R. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on
Scientific Computing, 1995, 16(2): 452–469. [doi: 10.1137/0916028]
[11] Gilbert JR, Miller GL, Teng SH. Geometric mesh partitioning: Implementation and experiments. SIAM Journal on Scientific Computing,
1998, 19(6): 2091–2110. [doi: 10.1137/S1064827594275339]
[12] Hager WW, Phan DT, Zhang HC. An exact algorithm for graph partitioning. Mathematical Programming, 2013, 137(1–2): 531–556. [doi:
10.1007/s10107-011-0503-x]
[13] Hendrickson B, Leland R. A multi-level algorithm for partitioning graphs. In: Proc. of the 1995 ACM/IEEE Conf. on Supercomputing.
San Diego: IEEE, 1995. 28.
[14] 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. [doi: 10.1137/S1064827595287997]
[15] Chevalier C, Pellegrini F. PT-Scotch: A tool for efficient parallel graph ordering. Parallel Computing, 2008, 34(6–8): 318–331. [doi: 10.
1016/j.parco.2007.12.001]
[16] Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970, 49(2): 291–307.
[doi: 10.1002/j.1538-7305.1970.tb01770.x]
[17] Fiduccia CM, Mattheyses RM. A linear-time heuristic for improving network partitions. In: Proc. of the 19th Design Automation Conf.
Las Vegas: IEEE, 1982. 175–181. [doi: 10.1109/DAC.1982.1585498]
[18] Stanton I, Kliot G. Streaming graph partitioning for large distributed graphs. In: Proc. of the 18th ACM SIGKDD Int ’l Conf. on
Knowledge Discovery and Data Mining. Beijing: ACM, 2012. 1222–1230. [doi: 10.1145/2339530.2339722]