Computer Science ›› 2022, Vol. 49 ›› Issue (6A): 594-600.doi: 10.11896/jsjkx.210400062

• Computer Network • Previous Articles     Next Articles

Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs

CHEN Jun-wu, YU Hua-shan   

  1. School of Computer Science,Peking University,Beijing 100871,China
  • Online:2022-06-10 Published:2022-06-08
  • About author:CHEN Jun-wu,born in 1996,master candidate.His main research interests include parallel computing and so on.
    YU Hua-shan,born in 1971,Ph.D,associate professor.His main research inte-rest include parallel and distributed computing.
  • Supported by:
    National Key R&D Program of China(2018YFB0204100).

Abstract: The single-source shortest path problem is an important graph primitive.It computes the shortest paths in a weighted graph from a source vertex to every other vertex.Combining the classical Dijkstra's algorithm and Bellman-Ford's algorithm,Δ-stepping algorithm is used widely to complete SSSP computations in parallel settings.Due to the generic mechanism of preferential attachment,most large-scale networks are significantly skewed in the vertex degree distributions.This paper presents two strategies that utilize the skewness to improve the efficiency and scalability of Δ-stepping algorithm on large graphs.A preprocessing is executed on the input graph to compute an upper bound for the distance between every pair of vertices.The preprocessing results are used to reduce the redundant edge relaxations in Δ-stepping algorithm,so to improve the algorithm's efficiency and scalability in parallels settings.First,these upper bounds are used to reduce the relaxed edges.An edge is skippable in the SSSP computation when its weight is greater than upper bound of the distance between the connected vertices.Second,they are used to reduce relaxations repeated on the same edges.During the computation,a vertex is forbidden to be relaxed before its tentative distance to the source vertex has been updated to be less than the upper bound.Experimental results show that the improved algorithm on the Graph500 benchmark graphs provides nearly 10 ×performance improvement over its implementation on Graph500,and the performance improvement is between 2.68 and 5.58 on some real graphs.

Key words: Large-scale graph, Performance optimization, Shortest path, Δ-stepping algorithm

CLC Number: 

  • TP311
[1] BERTSEKAS D P.Network Optimization:Continuous and Discrete Models[J].Athena Scientific,1998(9):877-877.
[2] AHUJA R K,MAGNANTI T L,ORLIN J B,et al.Networkflows-theory,algorithms and applications[J].Journal of the Operational Research Society,1993,45(11):791-796.
[3] MEYER U,SANDERS P.Δ-stepping:A parallel single source shortest path algorithm[C]//Proceedings of Annual European Symposium on Algorithms(Esa'98).1998:393-404.
[4] MEYER U,SANDERS P.Δ-stepping:a parallelizable shortestpath algorithm[J].Journal of Algorithms,2003,49(1):114-152.
[5] BLELLOCH G E,GU Y,SUN Y,et al.Parallel shortest paths using radius stepping[C]//Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures.2016:443-454.
[6] CHAKARAVARTHY V T,CHECCONI F,MURALI P,et al.Scalable single source shortest path algorithms for massively parallel systems[J].IEEE Transactions on Parallel and Distri-buted Systems,2016,28(7):2031-2045.
[7] BEAMER S,ASANOVIC K,PATTERSON D.Direction-opti-mizing breadth-first search[C]//Proceedings of the InternationalConference on High Performance Computing,Networking,Storage and Analysis(SC'12).IEEE,2012:1-10.
[8] DELLING D,GOLDBERG A V,NOWATZYK A,et al.PHAST:Hardware-accelerated shortest path trees[J].Journal of Parallel and Distributed Computing,2013,73(7):940-952.
[9] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world'networks[J].Nature,1998,393(6684):440-442.
[10] ALBERT-LASZLO B,ALBERT R.Emergence of Scaling inRandom Networks[J].Science,1999,286(5439):509-512.
[11] LESKOVEC J,CHAKRABARTI D,KLEINBERG J,et al.Kronecker graphs:an approach to modeling networks[J].arXiv:0812.4905v2,2009.
[12] MURPHY R C.WHEELER K B,BARRETT B W,et al.Introducing the graph 500[J].Cray User Group,2010,19:45-74.
[13] UENO K,SUZUMURA T.Highly scalable graph search for the Graph500 benchmark[C]//Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing.ACM,2012:149-160.
[14] ALBERT R,BARABÁSIA L.Statistical mechanics of complex networks[J/OL].
[1] WANG Yong, CUI Yuan. Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals [J]. Computer Science, 2022, 49(6A): 199-205.
[2] CHEN Le, GAO Ling, REN Jie, DANG Xin, WANG Yi-hao, CAO Rui, ZHENG Jie, WANG Hai. Adaptive Bitrate Streaming for Energy-Efficiency Mobile Augmented Reality [J]. Computer Science, 2022, 49(1): 194-203.
[3] E Hai-hong, ZHANG Tian-yu, SONG Mei-na. Web-based Data Visualization Chart Rendering Optimization Method [J]. Computer Science, 2021, 48(3): 119-123.
[4] ZHANG Xiao, ZHANG Si-meng, SHI Jia, DONG Cong, LI Zhan-huai. Review on Performance Optimization of Ceph Distributed Storage System [J]. Computer Science, 2021, 48(2): 1-12.
[5] ZHAO Xiao-wei, ZHU Xiao-jun, HAN Zhou-qing. Hover Location Selection and Flight Path Optimization for UAV for Localization Applications [J]. Computer Science, 2021, 48(11): 345-355.
[6] XU Jiang-feng and TAN Yu-long. Research on HBase Configuration Parameter Optimization Based on Machine Learning [J]. Computer Science, 2020, 47(6A): 474-479.
[7] ZHANG Peng-yi, SONG Jie. Research Advance on Efficiency Optimization of Blockchain Consensus Algorithms [J]. Computer Science, 2020, 47(12): 296-303.
[8] XU Chuan-fu,WANG Xi,LIU Shu,CHEN Shi-zhao,LIN Yu. Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python [J]. Computer Science, 2020, 47(1): 17-23.
[9] GENG Hai-jun, YIN Xia. Efficient Intra-domain Routing Protection Algorithm Based on i-SPF [J]. Computer Science, 2019, 46(8): 116-120.
[10] ZHANG Ling-hao, GUI Sheng-lin, MU Feng-jun, WANG Sheng. Clone Detection Algorithm for Binary Executable Code with Suffix Tree [J]. Computer Science, 2019, 46(10): 141-147.
[11] XU Qi-ze, HAN Wen-ting, CHEN Jun-shi, AN Hong. Optimization of Breadth-first Search Algorithm Based on Many-core Platform [J]. Computer Science, 2019, 46(1): 314-319.
[12] SUN Tao, ZHANG Jun-xing. Review of SDN Performance Optimization Technology [J]. Computer Science, 2018, 45(11A): 84-91.
[13] MAN Zhen-zhen, YU Shi-ming and HE De-feng. Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm [J]. Computer Science, 2017, 44(7): 215-220.
[14] ZUO Xiu-feng and SHEN Wan-jie. Improved Algorithm about Muti-shortest Path Problem Based on Floyd Algorithm [J]. Computer Science, 2017, 44(5): 232-234.
[15] LI Bing-kui, ZHUANG Lei, MA Ding, HU Ying, WANG Guo-qing and JING Chen-kai. Routing Mechanism Based on Business Differentiating in Software Defined Network [J]. Computer Science, 2017, 44(3): 118-122.
Full text



No Suggested Reading articles found!