收藏切换
A Distributed Buffered Streaming Graph Partitioning Algorithm
收藏切换
Huikang Shi1, Zesheng Wang2, Kekun Hu3, Gang Dong3, Youjian Zhao1, *
Journal of Computer Research and Development | 2025, 62(7) : 1805 - 1815
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(7): 1805-1815
• High Performance Computing •
A Distributed Buffered Streaming Graph Partitioning Algorithm
Full
Huikang Shi1, Zesheng Wang2, Kekun Hu3, Gang Dong3, Youjian Zhao1, *
Affiliations
  • 1Department of Computer Science and Technology, Tsinghua University, Beijing 100084
  • 2China Electronics Standardization Institute, Beijing 100007
  • 3IEIT SYSTEMS Co., Ltd., Jinan 250101
  • born in 1975. PhD. His main research interest includes electronic and information

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

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

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

    born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

About Author:

born in 1975. PhD. His main research interest includes electronic and information

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

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

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

born in 1969. PhD, professor, PhD supervisor. His main research interests include high-speed Internet architecture, Switching and routing, and high-speed network equipment

Published: 2025-07-01 doi: 10.7544/issn1000-1239.202330386
Outline
收藏切换

Graph partitioning is a key technique for parallel processing of big 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 propose a distributed streaming partitioning algorithm with a buffering mechanism in this paper. 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 with 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
史惠康, 王泽胜, 胡克坤, 董刚, 赵有健. 一种带缓冲区的分布式流式图划分算法. 计算机研究与发展, 2025 , 62 (7) : 1805 -1815 . DOI: 10.7544/issn1000-1239.202330386
Huikang Shi, Zesheng Wang, Kekun Hu, Gang Dong, Youjian Zhao. A Distributed Buffered Streaming Graph Partitioning Algorithm[J]. Journal of Computer Research and Development, 2025 , 62 (7) : 1805 -1815 . DOI: 10.7544/issn1000-1239.202330386
Year 2025 volume 62 Issue 7
101
43
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202330386
  • Receive Date:2023-05-23
  • Online Date:2026-11-10
  • Published:2025-07-01
Article Data
Affiliations
History
  • Received:2023-05-23
  • Revised:2025-01-24
  • Accepted:2025-03-03
Affiliations
    1Department of Computer Science and Technology, Tsinghua University, Beijing 100084
    2China Electronics Standardization Institute, Beijing 100007
    3IEIT SYSTEMS Co., Ltd., Jinan 250101
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330386
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT