A Shared-Memory Algorithm for Updating Single-Source Shortest Paths in Large Weighted Dynamic Networks

Sriram Srinivasan, Sara Riazi, Boyana Norris, Sajal K. Das, Sanjukta Bhowmick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages245-254
Number of pages10
ISBN (Electronic)9781538683866
DOIs
StatePublished - Feb 8 2019
Event25th IEEE International Conference on High Performance Computing, HiPC 2018 - Bengaluru, India
Duration: Dec 17 2018Dec 20 2018

Publication series

NameProceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018

Conference

Conference25th IEEE International Conference on High Performance Computing, HiPC 2018
CountryIndia
CityBengaluru
Period12/17/1812/20/18

Keywords

  • Dynamic Networks
  • Shared Memory
  • Single-Source Shortest Path
  • parallel graph algorithms

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'A Shared-Memory Algorithm for Updating Single-Source Shortest Paths in Large Weighted Dynamic Networks'. Together they form a unique fingerprint.

  • Cite this

    Srinivasan, S., Riazi, S., Norris, B., Das, S. K., & Bhowmick, S. (2019). A Shared-Memory Algorithm for Updating Single-Source Shortest Paths in Large Weighted Dynamic Networks. In Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018 (pp. 245-254). [8638105] (Proceedings - 25th IEEE International Conference on High Performance Computing, HiPC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HiPC.2018.00035