Paper Info
Title
A Shared-Memory Parallel Algorithm for Updating Single-Source Shortest Paths in Large Dynamic Networks.
Abstract
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.
Year
DOI
Venue
2018
10.1109/HiPC.2018.00035
HiPC
Keywords
Field
DocType
Heuristic algorithms,Software algorithms,Parallel algorithms,Partitioning algorithms,Scalability,Software,Memory architecture
Shortest path problem,Shared memory,Computer science,Parallel algorithm,Correctness,Parallel computing,Power graph analysis,Memory architecture,Computation,Scalability
Conference
ISSN
ISBN
Citations 
1094-7256
978-1-5386-8386-6
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Sriram Srinivasan137927.92
Sara Riazi210.69
Boyana Norris341739.46
Sajal K. Das48086745.54
Sanjukta Bhowmick512018.83