A Distributed Solution for Efficient K Shortest Paths Computation over Dynamic Road Networks

Our problem setting necessitates the following desirable properties in an index to support processing KSP queries.

(1) Low maintenance cost for dynamic graphs. Some existing index structures for processing shortest path queries maintain the shortest path between selected “landmark” vertices. However, when the edge weights of the graph constantly change, this becomes extremely expensive to maintain. As such, one of our requirements is that the index must be easy to maintain for dynamic graphs and imposes as little overhead as possible when the graph evolves.

(2) Suitable for deployment in a distributed setting. As the size of the graph and the number of concurrent queries keep increasing, a distributed index becomes a more attractive solution than a centralized one due to its ability to scale out. Since the graph $G$ itself may have to be partitioned and stored across the cluster, we should be able to maintain parts of the index on different nodes in a cluster corresponding to subgraphs of $G$.

(3) Supporting distributed algorithms. With the graph partitioned and subgraphs stored across the cluster, query processing takes place on different nodes in parallel. It is thus necessary for the index to assist the identification of relevant subgraphs that may contain pieces of the shortest paths to avoid examination of all subgraphs. Such an index should provide sufficient pruning power, and at the same time guarantee the correctness of the query result.

In view of the above requirements, we devise an index called DTLP that facilitates distributed KSP query processing over dynamic graphs. Based on a partitioning of $G$, DTLP has a two-level structure: the first level indexes each subgraph by maintaining a list of bounding paths (Section 3.4) between any pair of boundary vertices (Section 3.3). This provides the basis for computing the lower bounds of the shortest distances between the boundary vertices. The second level keeps a skeleton graph (Section 3.6) with all boundary vertices in all subgraphs, and it is computed based on the bounding paths identified in the first level. Fig. 1 illustrates the structure of the DTLP index.

The construction of DTLP starts with partitioning graph G into multiple subgraphs such that each subgraph has at most $z$ vertices. Different subgraphs may share vertices but not edges. For graph partitioning, we start from any vertex and traverse the graph $G$ using a breadth-first strategy to generate the subgraphs. The set of subgraphs is denoted as $\mathcal{S}$=$\{{SG}_{1}$, $\cdots$, $SG_{n}\}$ such that (1) $\mathcal{V}_{1}\cup\cdots\cup\mathcal{V}_{n}=\mathcal{V}$; (2) ${\mathcal{E}}_{1}\cup\cdots\cup{\mathcal{E}}_{n}=\mathcal{E}$; (3) ${\mathcal{W}}_{1}\cup\cdots\cup{\mathcal{W}}_{n}=\mathcal{W}$, where $n$ is the number of subgraphs and $SG_{i}=\{\mathcal{V}_{i},\mathcal{E}_{i},\mathcal{W}_{i}\}$ $(i\in[1,n])$.

The vertices shared by two or more subgraphs are called boundary vertices. Evidently, any path from a non-boundary vertex in $SG_{i}$ to a non-boundary vertex in $SG_{j}$ must pass through one or more boundary vertices, as those boundary vertices are the only ”contact vertices” between subgraphs.

Once graph partitions are in place, we move on to identify for each pair of boundary vertices in a subgraph a set of bounding paths. Bounding paths are specific paths in the subgraph serving as a reference to establish the bound distance, a stable lower bound of the shortest distance between the respective boundary vertices. The bounding paths do not change when the edge weights in the graph change, but the bound distances have to be updated to reflect the new information on edge weights. Those bounding paths will in turn be used to construct the skeleton graph.

As a first attempt, we consider utilizing the path(s) with the fewest edges between two boundary vertices as the bounding path(s). For any bounding path $P(i,j)$ with $m$ edges between two boundary vertices $v_{i}$ and $v_{j}$ in subgraph $SG$, the corresponding bound distance, denoted by $BD(P(i,j))$, is computed as the sum of the $m$ smallest edge weights in $SG$. It is easy to show that $BD(P(i,j))$ is not greater than the shortest distance between $v_{i}$ and $v_{j}$ in $SG$, but it very likely has a large discrepancy with the actual shortest distance. Next, we seek to further improve this bound in two ways. First, we identify more than one bounding path between a pair of boundary vertices, which provides more bound distances and we can choose the maximum one to narrow down the discrepancy with the actual shortest distance.

Second, we decompose the edge weight to finer granularity to provide better resolution when computing the bound distance. In particular, we assign virtual fragments (vfrags for short) for each edge in the graph $G$ and the number of vfrags of any edge $e_{i,j}$ equals to $w^{0}_{i,j}$, where $w^{0}_{i,j}$ is the initial weight of $e_{i,j}$ at the beginning of the DTLP construction. Such vfrags are additive, i.e., the number of vfrags on a path, $\phi(P(i,j))$, is the sum of the number of vfrags on each edge in the path. We call the weight of each vfrag in $e_{i,j}$ the unit weight, defined as ${w_{i,j}}/{w^{0}_{i,j}}$, where $w_{i,j}$ is the current weight of edge $e_{i,j}$, which varies over time. For any edge, the number of vfrags always remains the same, but the unit weight will change with varying weight.

With the two improvements above, we compute the bounding path and the bound distance as follows. For two boundary vertices $v_{i}$ and $v_{j}$, given a configurable parameter $\xi$, we compute a set $\mathcal{B}_{i,j}$ consisting of at most $\xi$ bounding paths that contain the least number of vfrags (where bounding paths containing the same number of vfrags are counted as only one path). Here, ${P^{\prime}_{l}}(i,j)$ ($l\in[1,|\mathcal{B}_{i,j}|]$) is called a bounding path, and ${P^{\prime}_{1}}(i,j)$ represents the bounding path with the fewest vfrags.

For a bounding path ${{P_{l}}^{\prime}}(i,j)$ from $v_{i}$ to $v_{j}$ in subgraph $SG$, we can compute a corresponding bound distance, which is the sum of the $\phi({{P_{l}}^{\prime}}(i,j))$ smallest unit weights in $SG$, denoted by $BD({{P_{l}}^{\prime}}(i,j))$.

Bounding paths are be computed in the initial graph offline and always remain the same regardless of the changing weights.

After identifying the set of bounding paths between $v_{i}$ and $v_{j}$ in subgraph $SG$, we aim to determine the bounding path that would impose as tight a lower bound on the shortest distance as possible. This translates to locating the maximal bound distance less than or equal to the shortest distance corresponding to this set of bounding paths. It will be referred to as the lower bound distance between $v_{i}$ and $v_{j}$, and the corresponding bounding path is called the lower bounding path.

To reach a tighter lower bound, recall that for each bounding path ${p_{l}}^{\prime}(i,j)$ between $v_{i}$ and $v_{j}$ in $SG$, its bound distance ($BD({p_{l}}^{\prime}(i,j))$) computed using vfrags is never greater than its actual distance ($D({p_{l}}^{\prime}(i,j))$). Consequently, if $D({p_{l}}^{\prime}(i,j))\leq BD({p_{g}}^{\prime}(i,j))$, we can conclude $D({p_{l}}^{\prime}(i,j))\leq D({p_{g}}^{\prime}(i,j))$. Exploiting this relationship allows us to identify the shortest path between $v_{i}$ and $v_{j}$ among the set of bounding paths in many cases. If this fails, however, we can still utilize the bounding path with the maximal bound distance as the lower bounding path. We detail this approach below.

Next, we introduce Theorem1¹¹1We have excluded the proofs for the theorems and lemmas in consideration of space limitations; however, they can be found in the appendix. to help identify the lower bound distance for a pair of boundary vertices.

Based on Theorem 1, we can identify the lower bounding paths and the lower bound distances between any pair of boundary vertices in each subgraph. Since any pair of boundary vertices $v$ can co-occur in more than one subgraph, there may be multiple lower bound distances associated with them, each for one subgraph. We call the least of these lower bound distances the minimum lower bound distance, denoted by $MBD(i,j)$, that provides the basis for constructing the skeleton graph in the Section 3.6.

The skeleton graph $G_{\lambda}$ contains all boundary vertices of all subgraphs. Any pair of boundary vertices $v_{i}$ and $v_{j}$ within the same subgraph is connected by edge $e^{\prime}_{i,j}$ with its weight being the minimum lower bound distance between $v_{i}$ and $v_{j}$. The rationale behind introducing the skeleton graph is that KSPs between two vertices in the original graph $G$ possibly pass through the same sequence of boundary vertices as their shortest paths in $G_{\lambda}$. Thus, $G_{\lambda}$ can provide an approximate search guideline to identify the different subgraphs in finding KSPs between a pair of vertices in $G$. Fig. 6 shows a skeleton graph $G_{\lambda}$ corresponding to the graph $G$ in Fig. 2.

EBP-II is an inverted index built for each subgraph. Each entity in EBP-II is a key-value pair, where the edges appearing in the bounding paths are viewed as keys and the value of each key (i.e., an edge) is the set of bounding paths containing the corresponding edge. The design of EBP-II is such that when the weight of an edge changes by $\Delta w$, we can immediately identify the bounding paths containing that edge, and update their actual distances by $\Delta w$. Subsequently, we compute the unit weights of the edge based on its new weight, and then update the bound distances of the bounding paths in the subgraph. Finally, for any two boundary vertices, if their bounding paths are impacted by the update on the actual or bound distances, we can easily update their lower bound distance as per Theorem 1. Fig. 7 shows a subgraph instance as well as the bounding paths between the boundary vertices $v_{1}$ and $v_{10}$, and its corresponding EBP-II is illustrated in Fig. 8.

EBP-II supports efficient maintenance of lower bound distances. However, it requires large storage overhead due to two major reasons: 1) a subgraph could contain a large number of edges, and therefore indexing them using edges as keys and set of bounding paths as values could lead to large storage overhead; and 2) there could be many duplicate bounding paths associated with different keys, which unnecessarily consumes extra storage. In view of these issues, we introduce an algorithm to compact EBP-II without sacrificing the maintenance efficiency.

The compaction strategy first partitions the key-value pairs in EBP-II into different sets with the purpose of assigning the values having as many common paths as possible into the same set. In this way, the shared paths corresponding to different values within the same set have a higher likelihood of being compacted. Following this, a Modified Prefix Tree (MPTree for short) is introduced to condense the repeated bounding paths in the values within each group. We describe the procedure in more detail below.

When the weight of an edge $e_{i,j}$ changes by $\Delta w$, we update the lower bound distances as follows. First, we identify the bounding paths covering $e_{i,j}$ based on G-MPTree. In particular, we first visit the root of G-MPTree to identify the subtree containing $e_{i,j}$, and then locate the tail node $e_{i,j}$ in the subtree based on the reference to $e_{i,j}$ kept by the root. Subsequently, we traverse upward $|\mathcal{P}_{i}|$ steps from $e_{i,j}$, where the visited normal nodes form $\mathcal{P}_{i}$, i.e., the set of bounding paths containing $e_{i,j}$. Finally, as discussed in Section 4.1, we update the actual and bound distances of the bounding paths in $\mathcal{P}_{i}$. After that, the lower bound distances between the corresponding boundary vertices as specified in Section 4.1 can be efficiently updated.

For a given query $q(v_{s},v_{t})$, the basic idea of KSP-DG is to use the shortest paths between $v_{s}$ and $v_{t}$ in $G_{\lambda}$ one by one (in increasing order of distance) as a reference path to identify the corresponding shortest paths in $G$ that have the same sequence of boundary vertices. This iterative process continues until the KSPs for the query are found. For this to succeed, one key observation is that the path between $v_{s}$ and $v_{t}$ in $G_{\lambda}$ is not longer than the path linking $v_{s}$ and $v_{t}$ in $G$ with the same sequence of boundary vertices. which is formally presented as follows.

KSP-DG is designed to run in a distributed cluster with the master-worker model. The master node maintains the original graph $G$, receives the weight updates for edges in $G$, and serves as the entry point of KSP queries. DTLP, as the fundamental index structure, is distributed across workers. In particular, the subgraphs resulting from partitioning $G$ are allocated to different workers on a many-to-one basis based on their load. Each worker maintains the assigned subgraphs as well as the bounding paths between boundary vertices (i.e., the first level of DTLP) within each subgraph. Moreover, a copy of the skeleton graph $G_{\lambda}$ (the second level of the DTLP index) is also kept on each worker.

Using the DLTP index, KSP-DG adopts a filter-and-refine strategy to iteratively find KSPs for the query $q(v_{s},v_{t})$. Each iteration of KSP-DG consists of two steps: filter and refine. Without loss of generality, we describe the two steps for the $i^{th}$ iteration.

In the filter step, we compute the $i^{th}$ shortest path between $v_{s}$ and $v_{t}$ in the skeleton graph $G_{\lambda}$, and use it as the reference path. This path corresponds to a sequence of boundary vertices, denoted by $\mathcal{R}$, between $v_{s}$ and $v_{t}$ in $G$. This step can be executed on one of the workers responsible for processing this query.

In the refine step, we aim to compute the corresponding k shortest paths connecting $v_{s}$ and $v_{t}$ in $G$ that traverse the same sequence of boundary vertices as those present in the reference path. Since any two adjacent boundary vertices in $\mathcal{R}$ must belong to the same subgraph, we can identify partial k shortest paths for each pair of adjacent boundary vertices in $\mathcal{R}$ from the corresponding subgraphs individually. This operation can be carried out by the workers maintaining those respective subgraphs in parallel. Next, the generated partial k shortest paths are reported back by these workers to the worker responsible for this query, which will then merge the partial k shortest paths received to form $k$ complete shortest paths, which all share the same sequence of boundary vertices as the reference path.

In each iteration, the generated k shortest paths corresponding to the reference path, called the candidate KSPs, are used to update a list $\mathcal{L}$ of the shortest paths that have been obtained so far. $\mathcal{L}$ keeps only k shortest paths found so far in ascending order of distance. After using the generated candidate KSPs to update $\mathcal{L}$ in the $i^{th}$ iteration, if the distance of the $k^{th}$ path in $\mathcal{L}$ is not greater than that of the reference path generated in the $(i+1)^{th}$ iteration, the algorithm terminates, and the paths in $\mathcal{L}$ are the final answer, i.e., the KSPs between $v_{s}$ and $v_{t}$ in $G$. Otherwise, the iteration continues.

Algorithm 1 shows the procedure of KSP-DG. It first initializes the parameters in Line 1, and then executes the filter and refine steps in each iteration in Lines 2-12, where $P^{\lambda}_{i}(s,t)$ denotes the $i^{th}$ reference path. The function candidateKSP is to identify the candidate KSPs for a given reference path, and its pseudo-code is shown in Algorithm 2. Line 6 in Algorithm 2 uses a Progressive Yen’s (PYen’s for short) Algorithm that will be discussed in Section 5.3.2 to compute the $k$-shortest paths in subgraph SG between the $j^{th}$ and $(j+1)^{th}$ vertices of the reference path.

Finding KSPs in directed graphs. KSP-DG can be adapted for KSP queries in directed graphs with minor DTLP index modifications. Instead of computing a single lower bound distance for a pair of boundary vertices $v_{i}$ and $v_{j}$, we maintain two sets of bounding paths and their corresponding lower bound distances, one for each direction (from $v_{i}$ to $v_{j}$ and vice versa). This modification transforms the skeleton graph into a directed one with two edges connecting each adjacent vertex pair, enabling KSP-DG to operate effectively for KSP search.

Non-boundary Vertices as Source or Destination. In scenarios where $v_{s}$ and/or $v_{t}$ are not boundary vertices, we address this by initially treating them as boundary vertices within subgraph $SG_{x}$ and $SG_{y}$ respectively. This tactical maneuver involves connecting $v_{s}$ to every boundary vertex $v_{i}$ in $SG_{x}$ and $v_{t}$ to every boundary vertex $v_{j}$ in $SG_{y}$ within the skeleton graph $G_{\lambda}$. These connections are made with edge weights set to the minimum lower bound distance between $v_{s}$ and $v_{i}$, and similarly for $v_{t}$. Afterward, both $v_{s}$ and $v_{t}$ are incorporated into $G_{\lambda}$, and the KSP-DG process, as outlined in Algorithm 1, is executed as if $v_{s}$ and $v_{t}$ were boundary vertices.

In the refinement step of KSP-DG, a computationally intensive yet frequently used operation involves calculating partial KSPs for specified pairs of boundary vertices within subgraphs. Typically, this task is performed using Yen’s algorithm, which can be inefficient. To address this inefficiency, we introduce PYen, a Progressive Yen’s algorithm designed to expedite this computation. In this section, we first provide an overview of Yen’s algorithm and then delve into the optimizations introduced in PYen.