An Algorithms of Distributed Buffered Streaming Graph Partitioning

Shi Huikang; Wang Zesheng; Hu Kekun; Dong Gang; Zhao Youjian

doi:10.7544/issn1000-1239.202330386

Journal of Computer Research and Development > 2025 > Accepted Manuscript > DOI: 10.7544/issn1000-1239.202330386 CSTR: 32373.14.issn1000-1239.202330386

Shi Huikang, Wang Zesheng, Hu Kekun, Dong Gang, Zhao Youjian. An Algorithms of Distributed Buffered Streaming Graph Partitioning[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202330386

Citation:

PDF (1771 KB)

An Algorithms of Distributed Buffered Streaming Graph Partitioning

1.
Department of Computer Science and Technology, Tsinghua University, Beijing 100084
2.
China Electronics Standardization Institute, Beijing 100007
3.
IEIT SYSTEMS Co., Ltd., Jinan 250101

More Information

Author Bio:
Shi Huikang: born in 1975. MD.His main research interests include electronic and information engineering

Wang Zesheng: born in 1987. PhD, senior engineer. His main research interests include cloud computing, information technology service

Hu Kekun: born in 1987.PhD, senior engineer. Member of CCF. His main research interests include big graph processing and graph deep learning

Dong Gang: born in 1979.PhD, senior engineer. Member of CCF. His main research interests include FPGA design, architecture and applications

Zhao Youjian: born in 1969.PhD, professor, PhD supervisor. His main research interests include High-speed Internet architecture, Switching and routing and High-speed network equipment
Received Date: May 22, 2023
Revised Date: January 23, 2025
Accepted Date: March 02, 2025
Available Online: March 02, 2025

Graphical Abstract

Abstract

Abstract

Graph partitioning is a key technique for parallel processing of large graphs. Existing graph partitioning algorithms struggle to balance partition quality and efficiency. Offline partitioning algorithms tend to achieve high partition quality but are time-consuming, while online (or streaming) partitioning algorithms are relatively efficient but suffer from suboptimal partition quality. To address the above problem, we in this work propose a distributed streaming partitioning algorithm with a buffering mechanism. The algorithm utilizes a multi-loader and multi-partitioner architecture, where multiple loaders read graph data in parallel to improve loading efficiency. Each partitioner maintains a buffer to store graph vertices received from the corresponding loader and sorts them in descending order based on vertex degree, providing better decision-making data for partitioning. Four streaming heuristic rules are pre-configured in the partitioners, which perform parallel partitioning on vertices in the buffer with different goals in mind. A reflow mechanism is employed to fine-tune the partitioning results and improve quality. Experimental results in a distributed system environment show that the proposed algorithm improves partition quality (edge-cut ratio) by more than 18.8% compared to the best existing online partitioning algorithm. Additionally, it reduces the proportion of graph data loading time in the total partitioning time from an average of 30.8% in a single-loader single-partitioner architecture to an average of 20.1%.
- big graph,
- streaming partitioning,
- distributed,
- buffering,
- restreaming

FullText(HTML)

References (32)

References

[1]	Sakr S, Boifati A, Voigt H, et al. The future is big graphs: A community view on graph processing systems[J]. Communications of the ACM, 2021, 64(9): 62−71 doi: 10.1145/3434642
[2]	杜玉洁,王志刚,王宁,等. 分布式多维大图迭代计算性能优化方法[J]. 计算机研究与发展,2023,60(3):654−675 doi: 10.7544/issn1000-1239.202110839 Du Yujie, Wang Zhigang, Wang Ning, et al. Optimization methods for distributed iterative computing performance over multi-dimensional large graph[J]. Journal of Computer Research and Development, 2023, 60(3): 654−675(in Chinese) doi: 10.7544/issn1000-1239.202110839
[3]	Fan W. Big graphs: Challenges and opportunities [C]// Proc of the 48th Int Conf on Very Large Data Bases, New York: ACM, 2022: 3782−3797
[4]	Zhai Xiaomeng, Zhang Hong, Huang Xu, et al. Graph partitioning strategies: One size does not fit all[J]. The Journal of Supercomputing, 2022, 78(17): 19272−19295 doi: 10.1007/s11227-022-04620-2
[5]	Dhillon I. Co-clustering documents and words using bipartite spectral graph partitioning [C]//Proc of the 7th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2001: 269−274
[6]	Karypis G, Kumar V. Multilevel graph partitioning schemes [C]// Proc of the 1995 Int Conf Parallel Processing. Piscataway, NJ: IEEE, 1995: 113−122
[7]	Jafari N, Selvitopi O, Aykanat C. Fast shared-memory streaming multilevel graph partitioning[J]. Journal of Parallel and Distributed Computing, 2021, 147(1): 140−151
[8]	Ji Shengwei, Bu Chenyang, Li Lei, et al. Local graph edge partitioning[J]. ACM Transactions on Intelligent Systems and Technology, 2021, 12(5): 1−25
[9]	Karypis G, Kumar V. Multilevel k-way partitioning scheme for irregular graphs[J]. Journal of Parallel and Distributed Computing, 1998, 48(1): 96−129 doi: 10.1006/jpdc.1997.1404
[10]	Stanton I, Kliot G. Streaming graph partitioning for large distributed graphs [C]// Proc of the 18th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1222−1230
[11]	Nishimura J, Ugander J. Restreaming graph partitioning: Simple versatile algorithms for advanced balancing [J]//Proc of the 19th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 1106−1114
[12]	Faraj M, Schulz C. Buffered streaming graph partitioning[J]. ACM Journal of Experimental Algorithmics, 2022, 27(1): 1−26
[13]	Tsourakakis C, Gkantsidis C, Radunovic B, et al. Fennel: streaming graph partitioning for massive scale graphs [C]// Proc of the 7th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2014: 333−342
[14]	Prabhakaran V, Wu M, Weng X, et al. Managing large graphs on multi-cores with graph awareness [C]// Proc of the 2012 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2012: 41−52
[15]	Awadelkarim A, Ugander J. Prioritized restreaming algorithms for balanced graph partitioning [C]// Proc of the 26th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2020: 1877−1887
[16]	Patwary M, Garg S, Kang B. Window-based streaming graph partitioning algorithm [C/OL]// Proc of the 2019 Australasian Computer Science Week Multiconference. New York: ACM, 2019[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_M7eaf008a16906a5f79aM765510178163167&pageSize=25&index=1&searchId=16b73b1aa0124198b09f65fff2d40076&resultsCount=2&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick
[17]	Faraj M, Schulz C. Buffered Streaming Graph Partitioning[J]. ACM Journal of Experimental Algorithmics, 2022, 27(9): 1−26
[18]	Hu Kekun, Zeng Gguosun, Jiang Huawen, et al. Partitioning big graph with respect to arbitrary proportions in a streaming manner[J]. Future Generation Computer Systems, 2018, 80(1): 1−11
[19]	Sun Zhipeng, Zeng Guosun, Ding Chunling, et al. A streaming graph partitioning method to achieve high cohesion and equilibrium via multiplayer repeated game[J]. IEEE Transactions on Computational Social Systems, 2022, 11(1): 803−814
[20]	Pacaci A, Özsu M. Experimental analysis of streaming algorithms for graph partitioning [C]// Proc of the 2019 Int Conf on Management of Data. New York: ACM, 2019: 1375−1392
[21]	Abbas Z, Kalavri V, Carbone P, et al. Streaming graph partitioning: An experimental study[J]. Proceedings of the VLDB Endowment, 2018, 11(11): 1590−1603 doi: 10.14778/3236187.3236208
[22]	Gottesbüren L, Heuer T, Sanders P, et al. Deep multilevel graph partitioning [C]// Proc of the 2021 European Symposium on Algorithms. Wadern, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_M6ed4f62317f8aacca4fM60ed1017816328&pageSize=25&index=3&searchId=34b88e32991449758b0b66925964e1eb&resultsCount=4&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick
[23]	Akhremtsev Y, Sanders P, Schulz C. High-quality shared-memory graph partitioning[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(11): 2710−2722 doi: 10.1109/TPDS.2020.3001645
[24]	Meyerhenke H, Sanders P, Schulz C. Parallel graph partitioning for complex networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(9): 2625−2638 doi: 10.1109/TPDS.2017.2671868
[25]	Battaglino C, Pienta R, Vuduc R. GraSP: Distributed streaming graph partitioning [C]// Proc of the 2015 High Performance Graph Mining, Barcelona, Spain: Barcelona Supercomputing Center, 2015[2023-04-21]. https://xueshu.baidu.com/usercenter/paper/show?paperid=9bb30523f8b9a6aa66ddf40fa944ca00&site=xueshu_se
[26]	Hanai M, Suzumura T, Tan Wenjun, et al. Distributed edge partitioning for trillion-edge graphs[J]. Proceedings of the VLDB Endowment, 2019, 12(13): 2379−2392 doi: 10.14778/3358701.3358706
[27]	Mayer C, Mayer R, Tariq M, et al. Adwise: Adaptive window-based streaming edge partitioning for high-speed graph processing [C]// Proc of the 38th IEEE Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2018: 685−695
[28]	Petroni F, Querzoni L, Daudjee K, et al. Hdrf: Stream-based partitioning for power-law graphs [C]// Proc of the 24th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2015: 243−252
[29]	Sajjad H, Payberah A, Rahimian F, et al. Boosting vertex-cut partitioning for streaming graphs [C]// Proc of the 5th IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2016[2023-04-21]. https://www.engineeringvillage.com/app/doc/?docid=cpx_4922c18f15887a4b174M79af10178163171&pageSize=25&index=1&searchId=9eb5c2ddc91c49e88880e18ea9b99248&resultsCount=1&usageZone=resultslist&usageOrigin=searchresults&searchType=Quick
[30]	Çatalyürek Ü, Devine K, Faraj M, et al. More recent advances in (hyper) graph partitioning[J]. ACM Computing Surveys, 2023, 55(12): 1−38
[31]	Stanford University. Snap dataset [DB/OL]. [2023-04-21]. http://snap.stanford.edu/data/index.html
[32]	Khorasani F, Gupta R, Bhuyan L. Scalable SIMD-efficient graph processing on GPUs [C]// Proc of the 24th Int Conf on Parallel Architecture and Compilation. Piscataway, NJ: IEEE, 2015: 39−50

[1]	Lu Sidi, He Yuankai, Shi Weisong. Vehicle Computing: An Emerging Computing Paradigm for the Autonomous Driving Era[J]. Journal of Computer Research and Development, 2025, 62(1): 2-21. DOI: 10.7544/issn1000-1239.202440538
[2]	Chen Xiao, Huang Muhong, Tian Yifan, Wang Yan, Cao Sheng, Zhang Xiaosong. Internet of Vehicles Data Sharing Scheme via Blockchain Sharding[J]. Journal of Computer Research and Development, 2024, 61(9): 2246-2260. DOI: 10.7544/issn1000-1239.202330899
[3]	Li Ke, Ma Sai, Dai Penglin, Ren Jing, Fan Pingzhi. Wireless Resource Allocation Algorithm Based on Multi-Objective Deep Reinforcement Learning for Vehicle-to-Vehicle Communications[J]. Journal of Computer Research and Development, 2024, 61(9): 2229-2245. DOI: 10.7544/issn1000-1239.202330895
[4]	Le Junqing, Tan Zhouyong, Zhang Di, Liu Gao, Xiang Tao, Liao Xiaofeng. Secure and Efficient Federated Learning for Continuous IoV Data Sharing[J]. Journal of Computer Research and Development, 2024, 61(9): 2199-2212. DOI: 10.7544/issn1000-1239.202330894
[5]	Tang Xiaolan, Liang Yuting, Chen Wenlong. Multi-Stage Federated Learning Mechanism with non-IID Data in Internet of Vehicles[J]. Journal of Computer Research and Development, 2024, 61(9): 2170-2184. DOI: 10.7544/issn1000-1239.202330885
[6]	Zheng Yingying, Zhou Junlong, Shen Yufan, Cong Peijin, Wu Zebin. Time and Energy-Sensitive End-Edge-Cloud Resource Provisioning Optimization Method for Collaborative Vehicle-Road Systems[J]. Journal of Computer Research and Development, 2023, 60(5): 1037-1052. DOI: 10.7544/issn1000-1239.202220734
[7]	Han Mu, Yang Chen, Hua Lei, Liu Shuai, Ma Shidian. Vehicle Pseudonym Management Scheme in Internet of Vehicles for Mobile Edge Computing[J]. Journal of Computer Research and Development, 2022, 59(4): 781-795. DOI: 10.7544/issn1000-1239.20200620
[8]	Yao Hailong, Yan Qiao. Cryptanalysis and Design of Anonymous Authentication Protocol for Value-Added Services in Internet of Vehicles[J]. Journal of Computer Research and Development, 2022, 59(2): 440-451. DOI: 10.7544/issn1000-1239.20200487
[9]	Tang Xiaolan, Xu Yao, Chen Wenlong. Bus-Data-Driven Forwarding Scheme for Urban Vehicular Networks[J]. Journal of Computer Research and Development, 2020, 57(4): 723-735. DOI: 10.7544/issn1000-1239.2020.20190876
[10]	Wang Xiufeng, Cui Gang, Wang Chunmeng. The Dynamical Prediction of V2V Link Duration in Urban VANETs[J]. Journal of Computer Research and Development, 2017, 54(12): 2721-2730. DOI: 10.7544/issn1000-1239.2017.20158391