高技术通讯2025，Vol.35Issue(2)：145-156,12.DOI:10.3772/j.issn.1002-0470.2025.02.004
基于数据压缩和异步通信策略的分布式图算法优化研究
Optimization of distributed graph algorithms based on data compression and asynchronous communication strategies
摘要
Abstract
Graph is a very important form of data structure,which is widely used in fields such as social networks,trans-portation networks and search engines.With the explosive growth of graph data size and limited storage capacity,distributed graph computation has become the focal point for processing large-scale graph data.Breadth-first search(BFS)algorithm is the basis of graph traversal and many graph analysis algorithms.There is a serious communica-tion overhead during distributed graph computation.To address the above problem,this paper proposes a compre-hensive data compression optimization scheme,combining bitmap and varint compression array,to reduce data communication overhead by high compression ratio;in addition,it also proposes a point-to-point asynchronous ring communication strategy to further reduce the synchronization overhead of computation-communication in distributed graph computing.Through these optimizations,this paper systematically evaluates the performance of BFS algorithm on an 8-node distributed cluster.When the graph data scale is 28,the average performance of BFS algorithm is 46.79 giga-traversed edges per second(GTEPS),and the performance has been improved by nearly 7.82％com-pared with that before the optimization.关键词
宽度优先搜索/图数据划分/压缩编码/异步环形通信/并行优化Key words
breadth first search(BFS)/graph partition/date compression/asynchronous ring communica-tion/parallel optimization引用本文复制引用
梁彦,聂娜,曹华伟,马丽娜,叶笑春,范东睿..基于数据压缩和异步通信策略的分布式图算法优化研究[J].高技术通讯,2025,35(2):145-156,12.基金项目
国家重点研发计划(2022YFB4501404)和北京市自然科学基金(4232036)资助项目. （2022YFB4501404）
