Skip to main content
Article
Single-Source Shortest Path Tree for Big Dynamic Graphs
Proceedings of the 2018 IEEE International Conference on Big Data (2018, Seattle, WA)
  • S. Riazi
  • S. Srinivasan
  • Sajal K. Das, Missouri University of Science and Technology
  • S. Bhowmick
  • B. Norris
Abstract

Computing single-source shortest paths (SSSP) is one of the fundamental problems in graph theory. There are many applications of SSSP including finding routes in GPS systems and finding high centrality vertices for effective vaccination. In this paper, we focus on calculating SSSP on big dynamic graphs, which change with time. We propose a novel distributed computing approach, SSSPIncJoint, to update SSSP on big dynamic graphs using GraphX. Our approach considerably speeds up the recomputation of the SSSP tree by reducing the number of map-reduce operations required for implementing SSSP in the gather-apply- scatter programming model used by GraphX.

Meeting Name
2018 IEEE International Conference on Big Data, Big Data 2018 (2018: Dec. 10-13, Seattle, WA)
Department(s)
Computer Science
Research Center/Lab(s)
Intelligent Systems Center
Second Research Center/Lab
Center for Research in Energy and Environment (CREE)
Third Research Center/Lab
Center for High Performance Computing Research
Keywords and Phrases
  • Apache Spark,
  • Big Dynamic Graphs,
  • Map- Reduce,
  • Single-Source Shortest Path (SSSP)
International Standard Book Number (ISBN)
978-153865035-6
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2019 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
12-1-2019
Publication Date
01 Dec 2019
Disciplines
Citation Information
S. Riazi, S. Srinivasan, Sajal K. Das, S. Bhowmick, et al.. "Single-Source Shortest Path Tree for Big Dynamic Graphs" Proceedings of the 2018 IEEE International Conference on Big Data (2018, Seattle, WA) (2019) p. 4054 - 4062
Available at: http://works.bepress.com/sajal-das/142/