TY - GEN
T1 - A Shared-Memory Algorithm for Updating Single-Source Shortest Paths in Large Weighted Dynamic Networks
AU - Srinivasan, Sriram
AU - Riazi, Sara
AU - Norris, Boyana
AU - Das, Sajal K.
AU - Bhowmick, Sanjukta
N1 - Funding Information:
Sanjukta Bhowmick and Sriram Srinivasan are supported by the NSF CCF Award #1533881 and #1725566. Sajal Das is supported by the NSF CCF Awards #1533918 and #1725755. Boyana Norris and Sara Riazi are supported by the NSF CCF Award #1725585.
Publisher Copyright:
© 2018 IEEE.
PY - 2019/2/8
Y1 - 2019/2/8
N2 - Computing the single-source shortest path (SSSP) is one of the fundamental graph algorithms, and is used in many applications. Here, we focus on computing SSSP on large dynamic graphs, i.e. graphs whose structure evolves with time. We posit that instead of recomputing the SSSP for each set of changes on the dynamic graphs, it is more efficient to update the results based only on the region of change. To this end, we present a novel two-step shared-memory algorithm for updating SSSP on weighted large-scale graphs. The key idea of our algorithm is to identify changes, such as vertex/edge addition and deletion, that affect the shortest path computations and update only the parts of the graphs affected by the change. We provide the proof of correctness of our proposed algorithm. Our experiments on real and synthetic networks demonstrate that our algorithm is as much as 4X faster compared to computing SSSP with Galois, a state-of-the-art parallel graph analysis software for shared memory architectures. We also demonstrate how increasing the asynchrony can lead to even faster updates. To the best of our knowledge, this is one of the first practical parallel algorithms for updating networks on shared-memory systems, that is also scalable to large networks.
AB - Computing the single-source shortest path (SSSP) is one of the fundamental graph algorithms, and is used in many applications. Here, we focus on computing SSSP on large dynamic graphs, i.e. graphs whose structure evolves with time. We posit that instead of recomputing the SSSP for each set of changes on the dynamic graphs, it is more efficient to update the results based only on the region of change. To this end, we present a novel two-step shared-memory algorithm for updating SSSP on weighted large-scale graphs. The key idea of our algorithm is to identify changes, such as vertex/edge addition and deletion, that affect the shortest path computations and update only the parts of the graphs affected by the change. We provide the proof of correctness of our proposed algorithm. Our experiments on real and synthetic networks demonstrate that our algorithm is as much as 4X faster compared to computing SSSP with Galois, a state-of-the-art parallel graph analysis software for shared memory architectures. We also demonstrate how increasing the asynchrony can lead to even faster updates. To the best of our knowledge, this is one of the first practical parallel algorithms for updating networks on shared-memory systems, that is also scalable to large networks.
KW - Dynamic Networks
KW - Shared Memory
KW - Single-Source Shortest Path
KW - parallel graph algorithms
UR - http://www.scopus.com/inward/record.url?scp=85062597031&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062597031&partnerID=8YFLogxK
U2 - 10.1109/HiPC.2018.00035
DO - 10.1109/HiPC.2018.00035
M3 - Conference contribution
AN - SCOPUS:85062597031
T3 - Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018
SP - 245
EP - 254
BT - Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 25th IEEE International Conference on High Performance Computing, HiPC 2018
Y2 - 17 December 2018 through 20 December 2018
ER -