An official website of the United States government
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.
more »
« less
Communication-Efficient ∆-Stepping for Distributed Computing Systems
This paper considers the single source shortest path (SSSP) problem, which is the key for many applications such as navigation, mapping, routing, and social networking. Existing SSSP algorithms are designed mostly for shared-memory systems. Nevertheless, with the prevalence of diverse smart devices like drones, there is a growing interest in deploying SSSP algorithms over distributed computing systems so that they can run efficiently onboard of smart devices via Mobile Ad Hoc Computing or at the network edges via Mobile Edge Computing. In this paper, we introduce a communication-efficient ∆-stepping algorithm for distributed computing systems. The proposed algorithm is featured by 1) a message coordination architecture for reducing message exchanges between workers, 2) a pruning technique for reducing redundant computations, and 3) an aggregation technique for further reducing message exchanges when communication delay is significant. Theoretical analyses and experimental studies on real-world graph datasets demonstrate the promising performance of proposed algorithm.
more »
« less
- Award ID(s):
- 2048266
- PAR ID:
- 10487278
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- 2023 19th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)
- ISBN:
- 979-8-3503-3667-2
- Page Range / eLocation ID:
- 369 to 374
- Format(s):
- Medium: X
- Location:
- Montreal, QC, Canada
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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.more » « less
-
Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)This paper presents parallel, distributed, and quantum algorithms for single-source shortest paths when edges can have negative integer weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in all these settings to n^{o(1)} calls to any SSSP algorithm that works on inputs with non-negative integer edge weights (non-negative-weight SSSP) with a virtual source. More specifically, for a directed graph with m edges, n vertices, undirected hop-diameter D, and polynomially bounded integer edge weights, we show randomized algorithms for negative-weight SSSP with - W_{SSSP}(m,n)n^{o(1)} work and S_{SSSP}(m,n)n^{o(1)} span, given access to a non-negative-weight SSSP algorithm with W_{SSSP}(m,n) work and S_{SSSP}(m,n) span in the parallel model, and - T_{SSSP}(n,D)n^{o(1)} rounds, given access to a non-negative-weight SSSP algorithm that takes T_{SSSP}(n,D) rounds in CONGEST, and - Q_{SSSP}(m,n)n^{o(1)} quantum edge queries, given access to a non-negative-weight SSSP algorithm that takes Q_{SSSP}(m,n) queries in the quantum edge query model. This work builds off the recent result of Bernstein, Nanongkai, Wulff-Nilsen [Bernstein et al., 2022], which gives a near-linear time algorithm for negative-weight SSSP in the sequential setting. Using current state-of-the-art non-negative-weight SSSP algorithms yields randomized algorithms for negative-weight SSSP with - m^{1+o(1)} work and n^{1/2+o(1)} span in the parallel model, and - (n^{2/5}D^{2/5} + √n + D)n^{o(1)} rounds in CONGEST, and - m^{1/2}n^{1/2+o(1)} quantum queries to the adjacency list or n^{1.5+o(1)} quantum queries to the adjacency matrix. Up to a n^{o(1)} factor, the parallel and distributed results match the current best upper bounds for reachability [Jambulapati et al., 2019; Cao et al., 2021]. Consequently, any improvement to negative-weight SSSP in these models beyond the n^{o(1)} factor necessitates an improvement to the current best bounds for reachability. The quantum result matches the lower bound up to an n^{o(1)} factor [Aija Berzina et al., 2004]. Our main technical contribution is an efficient reduction from computing a low-diameter decomposition (LDD) of directed graphs to computations of non-negative-weight SSSP with a virtual source. Efficiently computing an LDD has heretofore only been known for undirected graphs in both the parallel and distributed models, and been rather unstudied in quantum models. The directed LDD is a crucial step of the sequential algorithm in [Bernstein et al., 2022], and we think that its applications to other problems in parallel and distributed models are far from being exhausted. Other ingredients of our results include altering the recursion structure of the scaling algorithm in [Bernstein et al., 2022] to surmount difficulties that arise in these models, and also an efficient reduction from computing strongly connected components to computations of SSSP with a virtual source in CONGEST. The latter result answers a question posed in [Bernstein and Nanongkai, 2019] in the negative.more » « less
-
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.more » « less
-
Edge computing is increasingly proposed as a solution for reducing resource consumption of mobile devices running simultaneous localization and mapping (SLAM) algorithms, with most edge-assisted SLAM systems assuming the communication resources between the mobile device and the edge server to be unlimited, or relying on heuristics to choose the information to be transmitted to the edge. This paper presents AdaptSLAM, an edge-assisted visual (V) and visual-inertial (VI) SLAM system that adapts to the available communication and computation resources, based on a theoretically grounded method we developed to select the subset of keyframes (the representative frames) for constructing the best local and global maps in the mobile device and the edge server under resource constraints. We implemented AdaptSLAM to work with the state-of-the-art open-source V-and VI-SLAM ORB-SLAM3 framework, and demonstrated that, under constrained network bandwidth, AdaptSLAM reduces the tracking error by 62% compared to the best baseline method.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/WiMob58348.2023.10187809
