Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks

Shortest path query (SPQ) in road networks is a fundamental problem in graph analysis and has been widely studied due to its applications in various fields. Recently, with the proliferation of applications, the information of road networks becomes more complex and diversified, such as edge weight (e.g., transit time, toll fee) and edge label (e.g., toll road, trucks prohibited road). Existing works mainly aim to address the SPQ with minimum weight, i.e., find the shortest path with minimum distance or toll fee between two locations [1, 3, 6, 13, 16, 34]. However, the label information of edges can service more personalized scenarios. For example, if the drivers do not want to pay the toll fee, all toll roads should be neglected in the route planning [5]. Moreover, if a truck driver requires path service, the path returned should avoid all trucks prohibited roads [23]. The SPQ with considering the label constraints has many practical applications, such as personalized location-based services [35], logistics and commercial transportation [14]. [27] formalizes this problem as Label Constrained Shortest Path (LCSP) query. Formally, given a restricted label set R, LCSP query aims to find the shortest path with minimum weight avoiding the edges with labels in R. To efficiently answer the LCSP query, [27] proposes a novel index which is based on Contraction Hierarchies, namely Contraction Hierarchies with Label Restrictions (CHLR). In CHLR, a shortcut \(e=((u,v)\), w, l) denotes a path from u to v with weight w and label l. By shortening the path traversal, CHLR can significantly improve the LCSP query processing performance.

1.1 Motivation

In the real world, road networks can be dynamically changed. For each edge, the toll fee can be changed at any time by traffic department and the transit time is time-dependent due to the change of traffic conditions [25, 37]. Specifically, the traffic conditions can be updated by collecting the travel information of taxi-hailing app users and drivers (e.g., Didi, Uber). However, the number of app users and drivers is huge. In 2022, Didi has 15 million drivers and 493 million users [12], and Uber has 3.5 million drivers and 93 million users [10]. They can generate massive updates for traffic conditions per second. Accordingly, the edge weight can be dynamically changed at a high frequency. Moreover, the label of edges can be changed as well. For example, roads can be labeled as light traffic road, medium traffic road and heavy traffic road depending on the traffic conditions which will change in real time [22]. Unfortunately, most existing works for CHLR focus on static road networks and do not support the CHLR maintenance in dynamic road networks, which makes them unpractical for real applications. Motivated by this, in this paper, we study the CHLR maintenance problem in dynamic road networks.

1.2 Our Approach

To solve the CHLR maintenance problem in dynamic road networks, we first propose a \(\textsf{Baseline}\) approach. When an edge \(e_o\) changes its weight and label, a naive approach is to find all potential affected shortcuts due to the change of \(e_o\) and then recompute the affected shortcuts by invoking the existing CHLR construction algorithm [27]. However, the \(\textsf{Baseline}\) would recompute lots of shortcuts that actually do not change, which leads to expensive overhead of \(\textsf{Baseline}\). To overcome the drawbacks of \(\textsf{Baseline}\), in this paper, we devise a more efficient CHLR maintenance algorithm. Specifically, we design a novel update propagate chain to avoid massive invalid updates in \(\textsf{Baseline}\). In the update propagate chain, the neighborhood of shortcuts are defined as parents, child and partner. We observe that a shortcut only affects its child, and the weight of child can be obtained by its parents. We give an update order for the update propagate chain following the observation. Moreover, to further improve the efficiency, we propose an optimization strategy based on weight count of shortcuts, which can guarantee that shortcuts will only be recomputed when necessary. We prove that the optimized algorithm has a tightly theoretical boundedness in terms of the number of changed shortcuts \(E_\Delta\), i.e., \(O(|E_\Delta | \cdot log|E_\Delta | +|E_\Delta | \cdot d_{\textsf{max}})\), where \(d_{\textsf{max}}\) is the maximum degree.

In real applications, the travel platforms, like Didi and Uber, need to update their map service in a real-time fashion. As mentioned before, they update their traffic conditions based on the navigation data collected from app users and drivers who complete 30 million trips per day on average in Didi [12]. Similarly, more than 16 million trips are completed in Uber per day [10]. The navigation data further invoke the map service update. Faced with the massive updating requirements, a naive idea is to process them edge by edge. In this way, one shortcut may be updated multiple times due to different edge changes, which will lead to unnecessary time cost. Motivated by it, we further propose a batch index maintenance algorithm to process them batch by batch instead of one by one. We build the hierarchy of shortcuts by splitting shortcuts into multiple layers and prove that the shortcut updates on the same layer are independent. Hence, a parallel method is further proposed to process the edges on the same layer in parallel, which can accelerate calculations effectively.

1.3 Contributions

This paper has the following contributions.

1. 1.

   The first work for CHLR maintenance in dynamic road networks. In this paper, we aim to incrementally maintain the CHLR when the road networks are dynamically changed. To the best of our knowledge, this is the first work to address the CHLR maintenance problem in dynamic road networks.

2. 2.

   Efficient CHLR maintenance algorithms. In this paper, we devise an efficient CHLR maintenance algorithm. Specifically, we design a novel update propagate chain to only propagate the updated shortcuts, which can avoid massive invalid updates in \(\textsf{Baseline}\). Moreover, we propose an optimization strategy based on weight count of shortcuts, which can guarantee that shortcuts will only be recomputed when necessary. We prove that the optimized algorithm has a tightly theoretical boundedness.

3. 3.

   Optimized algorithms to handle batch update. To handle batch edge updates, we propose a batch index maintenance algorithm by building the hierarchy of shortcuts and updating shortcuts layer by layer in a bottom-up manner. We also show that shortcut changes within the same layer do not affect each other; thus, a parallel method is proposed to further improve the efficiency.

4. 4.

   Extensive experiments on the real road networks. We conduct extensive and comprehensive experiments on real road networks. As shown in our experiments, the optimized CHLR maintenance algorithm has good efficiency and effectiveness. It can achieve up to 2 orders of magnitude speedup compared with \(\textsf{Baseline}\). We also evaluate the efficiency of our batch index maintenance algorithm and parallel method.

2.1 Shortest Path Query in General Graphs

Graph analysis has been receiving increasing attention recently [7,8,9, 21, 32, 38]. Shortest path query in general graphs is an important problem in graph analysis [17, 26, 29, 30, 33, 40]. [29] computes the shortest path graph with exactly all shortest paths for any pair of vertices. [40] proposes a disk-based index that supports both single source distance queries and single source shortest path queries with small I/O and CPU costs. Both [26] and [30] provide parallel method to speed up shortest paths counting. [33] focuses on the constrained shortest path(CSP) query over a large time-dependent graph with time function and weight function on each edge. However, none of the above works consider the label information on edges, like toll road and trucks prohibited road, which are also important to help discover more personalized shortest paths. Considering the label information of edges, [17] studies the edge-constrained shortest path (ECSP) query problem where the target is to find a shortest path after filtering some edges based on user-specified query labels.

2.2 Shortest Path Indexes in Road Networks

In the literature, many shortest path query (SPQ) algorithms are proposed based on traditional methods, such as Dijkstra [13]; they compute the shortest path on weighted road networks directly. Recently, many index-based SPQ algorithms are proposed achieving remarkable results on speeding up the query process. Hub Labeling (HL) [1, 3, 18] is one of the most important shortest path indexes, which can improve the efficiency of SPQ by reducing the points on the shortest path. Pruned Landmark Labeling (PLL) [2] and Parallel Shortest-distance Labeling (PSL) [19] are further proposed based on HL. Arterial Hierarchy (AH) [39] index can improve the query time efficiently by splitting a graph into grid structure. Contraction Hierarchies (CH) [4, 11, 16] is a fundamental index that can reduce the number of iterations during the SPQ process by introducing shortcuts. Moreover, Hierarchical 2-Hop Labeling (H2H) [24] and P2H [6] combine the advantages of 2-hop labeling and hierarchy among all vertices. [27] studies the Label Constraint Shortest Path (LCSP) query problem in labeled and weighted road networks which can explore the shortest path \(P_{s,t}^R\) between two query vertices and avoid labels in R. Based on CH, [27] proposes an important shortest path index under the label restrictions (CHLR). In CHLR, there are a series of shortcuts \(e=((u,v),w,l)\), the shortcuts can build bridges among vertices to speed up the shortest path search process. Based on CHLR, the shortest path \(P_{s,t}^R\) can be found faster than online search. [27] also proposes an efficient CHLR construction algorithm. [20, 31] experimentally investigate the performance of different SPQ algorithms in multiple dimensions. In the above literature, most of them focus on the shortest path query on static road networks. However, in real world, the road networks can be constantly changed. Therefore, it is necessary to study the method of maintaining the shortest path index in dynamic road networks.

2.3 Shortest Path Index Maintenance in Dynamic Road Networks

In real world, road networks often change in practice. Hence, it is necessary to study the maintenance of shortest path indexes. [36] gives a solution for maintaining HL index in dynamic road networks. [6] introduces mechanisms for P2H index maintenance for edge weight updating. In order to maintain CH index, a number of methods [25] are proposed. Moreover, for the theoretical boundedness of the dynamic maintenance of CH and H2H, [37] presents the theoretical analysis according to the weight increase and decrease scenario separately. However, most of the existing works on dynamically maintaining shortest path indexes focus on the scenario with edge weight change. But the labels of the edges in road networks will be changed as well. To the best of our knowledge, for the important shortest path index CHLR, the corresponding index maintenance method is still to be investigated, which is studied in this paper.

Let \(G=(V,E,{\mathcalligra{w}},\Sigma ,{\mathcalligra{l}})\) be a directed, weighted and labeled road network, where V and E are the set of vertices and edges in the road network, respectively. \({\mathcalligra{w}}\) represents the weight function \({\mathcalligra{w}}: E\rightarrow \mathbb {R^{+}}\) mapping each edge to a positive weight number. \(\Sigma\) is a finite alphabet used for labeling edges in G and \({\mathcalligra{l}}\) is a function \({\mathcalligra{l}}: E\rightarrow \Sigma\) mapping edges to labels in \(\Sigma\). Besides, a vertex order function \(\phi : V\rightarrow \{1,\ldots , |V|\}\) is used to sort vertices in G. The neighbors of a vertex v are denoted as N(v). The neighbors with higher/lower order than v are denoted as \(N^{+/-}(v)\). We use n and m to denote the number of vertices and edges in the road network, respectively. A path in G is denoted as \(P_{s,t}=\{e_1,e_2, \ldots , e_k\}\) passing from s to t. The length of the path is expressed as \({\mathcalligra{w}}(P_{s,t})=\sum _{1\le i \le k}{\mathcalligra{w}}(e_i)\). The label of path is denoted as \({\mathcalligra{l}}(P_{s,t})={\mathcalligra{l}}(e_1)\cup {\mathcalligra{l}}(e_2)\cdots \cup {\mathcalligra{l}}(e_k)\). The order of P is the minimum order of vertices in the path, denoted as \(\phi (P)\). For simplicity, G is denoted as \(G=(V,E)\) if the context is self-evident. Note that the approach proposed in this paper can be smoothly adapted to undirected road networks as an undirected edge can be considered as two directed edges. The descriptions for the symbols and notations used in the paper are shown in Table 1.

Definition 1

(Label Constrained Shortest Path (LCSP)) Given a road network \(G=(V,E)\), a restricted label set R and two vertices s and t, the LCSP under restricted labels R from s to t is a path \(P_{s,t}^R=\{e_1,e_2, \ldots , e_k\}\), such that (1) for \(1 \le i\le k\), \({\mathcalligra{l}}(e_i)\cap R =\emptyset\), i.e., the path avoids all restricted labels in R; (2) \({\mathcalligra{w}}(P_{s,t}^R)\) is minimum, i.e., \(P_{s,t}^R\) is the shortest path satisfying condition (1).

An example for road network G and CHLR on G

Full size image

Example 1

Considering the road network G shown in Fig. 1a, for a LCSP query with \(s=v_{11}\), \(t=v_9\), \(R=\{c\}\), there are two LCSPs \(P_1=\{(v_{11},v_2),(v_2,v_8),(v_8,v_9)\}\) and \(P_2=\{(v_{11},v_{10}),(v_{10},v_9)\}\). For both paths, the length is 7, the restricted label c is avoided, and there is no other path shorter than them without label c.

3.1 Contraction Hierarchies with Label Restrictions

To address LCSP query efficiently, [27] proposes a novel shortest path index based on Contraction Hierarchies (CH) with label restrictions.

Definition 2

(Contraction Hierarchies with Label Restrictions (CHLR) Given a road network \(G=(V,E)\) and a vertex order function \(\phi\), for two edges \(e'=(u,q)\) and \(e''=(q,v)\) where \(\phi (q)<\phi (u)\), \(\phi (q)<\phi (v)\), a shortcut \(e=((u,v),w,l)\) is created with \(w={\mathcalligra{w}}(e')+{\mathcalligra{w}}(e'')\) and \(l={\mathcalligra{l}}(e')\cup {\mathcalligra{l}}(e'')\) if there is no path \(P'\) shorter than \(P=\{e',e''\}\) satisfying \(\phi (P')>\phi (P)\) and \({\mathcalligra{l}}(P')\subseteq {\mathcalligra{l}}(P)\). The CHLR index on G is the set of shortcuts, denoted as \(E'\). The road network with CHLR is called augmented graph, denoted as \(G'=(V,E\cup E')\).

Note that e can represent a shortcut or an original edge depending on the context. To distinguish them, since a shortcut \(e=((u,v),w,l)\) may also be an original edge in G, the ‘edge’ is only be used to denote the original edge in G. Moreover, e can be simplified as \(e=(u,v)\) when the context is self-evident.

Example 2

Considering the road network G in Fig. 1a, the order of each vertex is marked close the vertex. The CHLR index on G is shown in Fig. 1b, which is represented in blue dotted lines. For instance, shortcut \(e'=((v_{1},v_9),4\), \(\{a,b,c\})\) is a shortcut for edges \((v_{1},v_{3})\) and \((v_{3},v_9)\), as \(\phi (v_{3})<\phi (v_{1})\), \(\phi (v_{3})<\phi (v_9)\) and there is no path \(P'\) from \(v_1\) to \(v_9\) shorter than \(P=\{(v_1,v_3),(v_3,v_9)\}\) satisfying \(\phi (P')>\phi (P)\) and \({\mathcalligra{l}}(P')\subseteq {\mathcalligra{l}}(P)\).

3.2 CHLR-based LCSP Query

Given a road network G, and \(G'\) with CHLR, to address a LCSP query for \(P_{s,t}^R\), the result can be retrieved by using a bidirectional Dijkstra query variant which performs a simultaneous forward query from s in upward graph \(G'^\uparrow\) and backward query from t in the downward graph \(G'^\downarrow\), where \(E(G'^\uparrow )=\{e=(u,v)|\phi (u)<\phi (v)\wedge {\mathcalligra{l}}(e)\cap R=\emptyset \}\) and \(E(G'^\downarrow )=\{e=(u,v)|\phi (u)>\phi (v)\wedge {\mathcalligra{l}}(e)\cap R=\emptyset \}\). The query terminates once the minimum key for the priority queue of Dijkstra’s algorithm exceeds the tentative shortest distance and \(P_{s,t}^R\) on G is obtained.

3.3 CHLR Construction

Given a road network G and a vertex order function \(\phi\), CHLR can be constructed through contracting vertices in the increasing order of \(\phi\). When contracting a vertex q, based on Definition 2, for each pair of neighbors (u, v) in \(N^+(q)\), a potential shortcut \(e=(u,v)\) is considered with \({\mathcalligra{l}}(e)={\mathcalligra{l}}((u,q))\cup {\mathcalligra{l}}((q,v))\) and \({\mathcalligra{w}}(e)={\mathcalligra{w}}((u,q))+{\mathcalligra{w}}((q,v))\). If there is a path \(P'\) shorter than \(P=\{(u,q),(q,v)\}\) satisfying \(\phi (P')>\phi (P)\) and \({\mathcalligra{l}}(P')\subseteq {\mathcalligra{l}}(P)\), e is unnecessary and can be omitted in \(G'\). Otherwise, e is created as a shortcut and inserted into \(G'\). \(P'\) can be retrieved by Dijkstra’s algorithm from u to v through vertices with higher order than q and edges with labels in \({\mathcalligra{l}}(P)\). When all vertices are contracted, all shortcuts in CHLR are obtained.

3.4 Problem Statement

In this paper, we investigate the CHLR maintenance problem on dynamic road networks. Given a road network G and edge change including weight increase/ decrease and label change, we incrementally update the CHLR index on G after the edge change.

To address the CHLR maintenance problem, in this section, we first explore a \(\textsf{Baseline}\) approach. Considering a changed edge \(e=(q,v)\) with new weight or label, the main idea of \(\textsf{Baseline}\) is to explore the affected shortcuts and recompute the affected shortcuts. There are two steps: (1) Explore the affected shortcuts. Due to the change of \(e=(q,v)\), assuming \(\phi (q)<\phi (v)\), the shortcuts like \(e'=(u,v)\) produced by contracting q and incident to e may be changed. As \(e'\) can be updated by recontracting q who can produce \(e'\), q is marked as the vertex to be recontracted and stored into \(\Theta\). Recursively, the change of \(e'\) may further affect more shortcuts. Similarly, the vertices supporting the affected shortcuts are stored into \(\Theta\). (2) Recompute the affected shortcuts. When all effected shortcuts are explored, they can be updated by recontracting the vertex in \(\Theta\) by invoking the existing CHLR construction algorithm [27].

Example 3

Consider the road network G shown in Fig. 1a. If an edge \(e=((v_4,v_6),5,\{b\})\) is changed to \(e=((v_4,v_6),1\), \(\{c\})\), following the \(\textsf{Baseline}\), at step 1, the vertices to be recontracted in \(\Theta\) are \(\{v_4,\ldots ,v_7,v_{11},v_{12}\}\). Then, we recontract them in the increasing order of \(\phi\) at step 2. For instance, when recontracting \(v_4\), it will produce two new shortcuts \(e_1=((v_5,v_6),3,\{b,c\})\) and \(e_2=((v_7,v_6),6,\{a,c\})\).

Theorem 1

Given a road network G and a changed edge e, the time complexity of \(\textsf{Baseline}\) to update CHLR index is \(O(|\Theta | \cdot d_{\textsf{max}} ^2 \cdot m \cdot logn)\), where \(d_{\textsf{max}}\) is the maximum degree of vertices in \(G'\).

Proof

At step 1, for each affected shortcut e, exploring the shortcuts that e further affects and finding the vertices that can update e consume \(O(d_{\textsf{max}})\) time, and the number of the affected shortcuts is \(O(|\Theta |)\). Next, at step 2, for each vertex in \(\Theta\), it can produce \(O(d_{\textsf{max}} ^2)\) shortcuts. Furthermore, to generate a shortcut, [27] invokes Dijkstra’s algorithm with time complexity \(O(m \cdot logn)\). Therefore, the total time complexity of \(\textsf{Baseline}\) is \(O(|\Theta | \cdot d_{\textsf{max}} ^2 \cdot m \cdot logn)\). \(\square\)

4.1 Drawbacks of \(\textsf{Baseline}\)

Unfortunately, the \(\textsf{Baseline}\) approach may introduce unnecessary overhead. First, the affected shortcuts explored at step 1 may do not change their weights and labels. Second, at step 2, all shortcuts incident to vertices in \(\Theta\) will be recomputed by vertex contraction. However, most of them are unchanged in fact. All of these lead to unnecessary overhead of \(\textsf{Baseline}\).

In this section, we explore a new CHLR maintenance algorithm to update index more efficiently by avoiding the overhead of \(\textsf{Baseline}\) for unchanged shortcuts.

5.1 Framework

Considering a road network G and a changed edge e, due to the weight or label change of e, we can recursively update shortcuts in a BFS-like way. In our new CHLR maintenance algorithm, we aim to reveal an update propagate chain among shortcuts. Only when current shortcut \(e'\) is changed, it will extend the update propagate chain to update more shortcuts incident to \(e'\). In this way, the unnecessary overhead of \(\textsf{Baseline}\) for updating unchanged shortcuts can be reduced sharply.

Definition 3

(Neighborhood of Shortcuts) Given the CHLR index on the road network G, for a shortcut \(e=(u,v)\) and two shortcuts \(e'=(u,q)\) and \(e''=(q,v)\), if \(\phi (q)<\phi (u)\), \(\phi (q)<\phi (v)\) and \({\mathcalligra{l}}(e)={\mathcalligra{l}}(e')\cup {\mathcalligra{l}}(e'')\), then, \(e'\) and \(e''\) are the parents of e, denoted as \((e',e'')\in N^-(e)\). e is the child of \(e'\) and \(e''\), denoted as \(e=N^+(e',e'')\). \(e'\) is a partner of \(e''\), denoted as \(e'\in N^=(e'')\).

Lemma 1

Given a road network G and a shortcut e, the weight of e can be computed by \({\mathcalligra{w}}(e)=min\{w,{\mathcalligra{w}}(e')+{\mathcalligra{w}}(e'')| \forall (e',e'')\in N^-(e)\}\), where w is the weight of e in G if e is an original edge in G.

5.2 Algorithm of \(\textsf{CalWeight}\)

Based on Lemma 1, we first propose a weight calculation algorithm to compute the weights of shortcuts on the augmented graph \(G'\), which is named \(\textsf{CalWeight}\). The pseudocode is shown in Algorithm 1. Since the pseudocode is self-explanatory, we omit the detailed description for brevity. Note that \({\textsf{cnt}}\) of Algorithm 1 can be ignored here which will be introduced later.

After obtaining the weights of shortcuts, based on Definition 2, the shortcuts with same (u, v) but different labels may conflict with each other in \(G'\). For instance, there are two shortcuts \(e=((u,v),w_1,\{a,b\})\) and \(e'=((u,v),w_2\), \(\{a,b,c\})\), \(w_1<w_2\). Then, for any LCSP query with restricted label set R, if the target \(P_{s,t}^R\) passes through u and v, e has higher priority than \(e'\) and \(P_{s,t}^R\) will never pass through \(e'\). It’s because \(e'\) has heavier weight and stricter label constraint than e. To distinguish the conflict relationship, we propose the formal definition of shortcut dominance below.

Definition 4

(Shortcut Dominance) Given a road network G and CHLR on G, considering two shortcuts e and \(e'\) for vertices u and v with different weights or labels, if \({\mathcalligra{w}}(e)\le {\mathcalligra{w}}(e')\) and \({\mathcalligra{l}}(e)\subset {\mathcalligra{l}}(e')\), then e dominates \(e'\), \(e'\) is dominated by e. \(\Phi (e)\) is the dominant shortcut set of e, \(e'\in \Phi (e)\).

Lemma 2

Given a road network G and CHLR on G, considering two shortcuts e and \(e'\), if e dominates \(e'\), then \(e'\) can be removed from CHLR safely.

5.3 Algorithm of \(\textsf{KeepSCDom}\)

Following Lemma 2, we propose a \(\textsf{KeepSCDom}\) algorithm to keep the shortcut dominance, the pseudocode is shown in Algorithm 2. Given a shortcut e, \(\textsf{type}\) is used to mark the weight increase or decrease of e, Q is a priority queue to store the changed shortcuts. Based on Definition 4, if e can be dominated by \(e'\) in the augmented graph \(G'\), e is marked as invalid shortcut in \(G'\), the weight of e is assigned as \(\infty\) (line 1–2). Otherwise, if the weight of e increases, we recompute the weight of shortcut \(e'\) in \(\Phi (e)\), if \({\mathcalligra{w}}(e')<{\mathcalligra{w}}(e)\), \(e'\) is not dominated by e anymore. In this case, \(e'\) becomes valid in \(G'\) (line 4–9). On the other hand, if the weight of e decreases, it can dominate more shortcuts who have heavier weight and longer label than e. Such dominated shortcuts become invalid in \(G'\) (line 10–14). Since the weights of shortcuts in line 9 and line 14 are updated, they are pushed into Q to further update more shortcuts.

Now, we analyze the update propagate chain among shortcuts.

Definition 5

(Update Propagate Chain) When the weight of a shortcut e decreases or increases, e only changes its child shortcuts \(e''\) in \(N^+(e,e')\), where \(e'\) is a partner of e in \(N^=(e)\). Specifically,

• when \({\mathcalligra{w}}(e)\) decreases, update \({\mathcalligra{w}}(e'')={\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\) if \({\mathcalligra{w}}(e'') > {\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\);

• when \({\mathcalligra{w}}(e)\) increases, recompute \({\mathcalligra{w}}(e'')\).

If \({\mathcalligra{w}}(e'')\) changes, \(\textsf{KeepSCDom}\) algorithm is utilized to keep the shortcut dominance and \(e''\) is pushed into Q to be the next shortcut of the update propagate chain.

Example for update process of \(\textsf{CHLRMaintenance}\) algorithm

Full size image

Definition 6

(Update Order) Given the augmented graph \(G'\), the update order of edges \(e=((u,v),w,l)\) is the order to be processed in the priority queue Q, denoted as \(\phi (e)\). For other arbitrary edge \(e'=((u',v'),w',l')\), \(\phi (e)<\phi (e')\) if \(min\{\phi (u),\phi (v)\}<min\{\phi (u'),\phi (v')\}\) or \(min\{\phi (u),\phi (v)\}\) = \(min\{\phi (u'),\phi (v')\}\) and \(|l|<|l'|\).

Theorem 2

Based on Definition 5 and Definition 6, when an edge change for e arrives, performing the update propagate chain from e and propagating the update following the update order can update CHLR correctly.

Proof

Theorem 2 holds based on two significant facts. (1) Given an updated shortcut e, e only affects its child shortcuts \(e''\). The weight of \(e''\) can be updated following Definition 5. Specifically, if \({\mathcalligra{w}}(e)\) decreases, it only needs to determine whether e will produce a shorter path for \(e''\), if so, \({\mathcalligra{w}}(e'')={\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\). Otherwise, if \({\mathcalligra{w}}(e)\) increases, it’s necessary to recompute \({\mathcalligra{w}}(e'')\) by invoking \({\textsf{CalWeight}}\). This is because due to the weight increase of e, the shortest path for \(e''\) may be destroyed by e and a new shortest path should be generated by other parents of \(e''\). Moreover, for other shortcuts incident to e but with lower order than e, since e will only affect the shortcuts with higher order than it based on the contracting process of CHLR, they will not be affected by e. (2) For accuracy guarantee, parents shortcuts should be updated before their child shortcut. By Definition 3 and Definition 6, for shortcut \(e'' = N^+(e,e')\), we have \(\phi (e)<\phi (e'')\) and \(\phi (e')<\phi (e'')\). Hence, updating the shortcut with lowest order in Q at each time ensures that their child shortcut will be updated correctly as the weights of their parents shortcuts are up to date now. In this way, CHLR can be updated correctly. \(\square\)

5.4 Algorithm of \(\textsf{CHLRMaintenance}\)

Based on Theorem 2, we propose our CHLR maintenance algorithm, the pseudocode is shown in Algorithm 3. Given the augmented graph \(G'\), a changed edge \(e_o\) with new weight \(w_n\) and new label \(l_n\), we first update \(e_o\) and create \(e_n\) with new weight and label (line 2–8). If the label of \(e_o\) is changed, we compute the weight of \(e_o\) with old label, if the weight increases, \(e_o\) is pushed into Q with \({\textsf{type}}\)=‘inc’, meanwhile, if weight of \(e_n\) with new label decreases, \(e_n\) is pushed into Q with \({\textsf{type}}\)=‘dec’ (line 3–5). Otherwise, \(e_o\) is pushed into Q depending on the weight increase or decrease (line 7–8). After that, the update propagate chain starts. At each time, Q selects the shortcut e with lowest order \(\phi (e)\) to propagate update. Following the update rules in Definition 5, we update the weight of each child \(e''\) of e. If the weight of e increases, the weight of \(e''\) is recomputed by invoking \({\textsf{CalWeight}}\) algorithm. And if \({\mathcalligra{w}}(e'')\) increases due to e, \(e''\) is pushed into Q with \({\textsf{type}}\)=‘inc’ and invokes \(\textsf{KeepSCDom}\) algorithm (line 14–18). On the other hand, if the weight of e decreases, we just update the weight of \(e''\) directly if \({\mathcalligra{w}}(e'')>{\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\). Then, \(e''\) is pushed into Q and invokes \(\textsf{KeepSCDom}\) algorithm if \({\mathcalligra{w}}(e'')\) decreases (line 19–23). When all shortcuts in Q finish their update propagation, we obtain the new CHLR on \(G'\) correctly.

Example 4

Considering the road network G in Fig. 1a and CHLR on G shown in Fig. 1b, the neighborhood of shortcuts is shown in Fig. 2. Given an updated edge \(e_o=((v_4,v_6)\), \(5,\{b\})\), and new weight 7 and new label \(\{c\}\) for \(e_o\), following Algorithm 3, as the label of \(e_o\) changes, \(e_o\) becomes \(((v_4,v_6),\infty\), \(\{b\})\) and is pushed into Q with \({\textsf{type}}\)=‘inc’, while \(e_n=((v_4,v_6),7,\{c\})\) is created and pushed into Q with \({\textsf{type}}\)=‘dec’. Then, \(e_o\) first updates its child shortcuts \(e_1=((v_5,v_6),7,\{b\})\) and \(e_2=((v_7,v_6),7,\{a,b\})\). As the weight of \(e_o\) is \(\infty\) now, we recompute \({\mathcalligra{w}}(e_1)\) and \({\mathcalligra{w}}(e_2)\), their weights are unchanged. Next, \(e_n\) produces two new child shortcuts \(e_3=((v_5,v_6),9,\{b,c\})\) and \(e_4=((v_7,v_6),12\), \(\{a,c\})\). Here, based on Definition 4, \(e_1\) can dominate \(e_3\) as \({\mathcalligra{w}}(e_1)<{\mathcalligra{w}}(e_3)\) and \({\mathcalligra{l}}(e_1)\subset {\mathcalligra{l}}(e_3)\); therefore, \(e_3\) is invalid in \(G'\). Subsequently, \(e_4\) further produces a new child shortcut \(e_5=((v_{11},v_6),16\), \(\{a,b,c\})\). Now, Q is empty, the algorithm finishes.

Example for update process of \(\mathsf {CHLRMaintenance^*}\) algorithm

Full size image

5.5 Optimization Strategy

To further improve the efficiency of CHLR maintenance, we explore an optimization strategy based on the following observation. Reconsidering the update operation of Algorithm 3, for a shortcut e from Q, when the weight of a shortcut e increases, we have to recompute the weight of each child shortcut \(e''\) of e (line 16 of Algorithm 3) whenever \({\mathcalligra{w}}(e'')\) will change or not. However, if e does not support the current weight of \(e''\), i.e., \({\mathcalligra{w}}(e'')<{\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\) where e and \(e'\) are the parents of \(e''\), \({\mathcalligra{w}}(e'')\) will not be affected by e. Moreover, even e and \(e'\) can support the current weight of \(e''\), i.e., \({\mathcalligra{w}}(e'')={\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\), if there exists another couple of parents \(e_1\) and \(e'_1\) that can support \({\mathcalligra{w}}(e'')\), \({\mathcalligra{w}}(e'')\) will not change as well. To avoid the invalid computation for weight, we propose an optimized CHLR maintenance algorithm based on weight count. We first give the definition of weight count.

Definition 7

(Weight Count) Given a road network G and the CHLR on G, for each shortcut e in CHLR, the weight count of e is the number of parents that can support the weight of e, denoted as \({\textsf{cnt}} (e)\), i.e., \({\textsf{cnt}} (e)\) = \(|\{(e_1,e_2)|{\mathcalligra{w}}(e)\) = \({\mathcalligra{w}}(e_1)+{\mathcalligra{w}}(e_2), (e_1,e_2)\in N^-(e)\}|\). Note that if e is an original edge in G with weight \({\mathcalligra{w}}(e)\), \({\textsf{cnt}} (e)\) is increased by one.

Lemma 3

In the update propagate chain, when the weight of a shortcut e increases, for e’s each child shortcut \(e''\), \(e''= N^+(e,e')\), if \({\mathcalligra{w}}(e'')<{\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\) or \({\textsf{cnt}} (e'')>1\), \({\mathcalligra{w}}(e'')\) will not change, the weight update for \(e''\) can be skipped safely.

5.6 Algorithm of \(\mathsf {CHLRMaintenance^{*}}\)

Following Lemma 3, we devise our optimized algorithm \(\mathsf {CHLRMaintenance^*}\). The pseudocode is shown in Algorithm 4. Given the augmented graph \(G'\), a changed edge \(e_o\), new weight \(w_n\) and new label \(l_n\) for \(e_o\), we first update the weight count \({\textsf{cnt}}\) for \(e_o\) and \(e_n\). The weight \({\mathcalligra{w}}(e_o)\) is destroyed, \({\textsf{cnt}} (e_o)\) is assigned as 0 and \(e_o\) is pushed into Q with \(\textsf{type}\) =‘inc’ (line 3). For shortcut \(e_n\), if \({\mathcalligra{w}}(e_n)=w_n\), we increase \({\textsf{cnt}} (e_n)\) by one (line 4). Besides, if \({\mathcalligra{w}}(e_n)\) decreases due to \(w_n\), \({\textsf{cnt}} (e_n)\) is assigned as 1 and \(e_n\) is pushed into Q with \(\textsf{type}\) =‘dec’ (line 5). On the other hand, if the label of \(e_n\) is unchanged, \({\textsf{cnt}} (e_o)\) can be updated similarly depending on the change of \({\mathcalligra{w}}(e_o)\) (line 7–10). After that, the update propagate chain starts from the shortcuts in Q. At each time, Q selects the shortcut e with lowest order \(\phi (e)\) to propagate update. If e will increase its weight, for each child shortcut \(e''\), \(e''= N^+(e,e')\), based on Lemma 3, only if \({\textsf{cnt}} (e'')\ge 1\) and \({\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')={\mathcalligra{w}}(e'')\), \({\textsf{cnt}} (e'')\) is decreased by 1. Then, if \({\textsf{cnt}} (e'')<1\), \(e''\) is pushed into Q with \(\textsf{type}\) =‘inc’ (line 15–18). Otherwise, if e has decreased its weight and \({\mathcalligra{w}}(e'') = {\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\), then we add \({\textsf{cnt}} (e'')\) by 1. If \({\mathcalligra{w}}(e'') > {\mathcalligra{w}}(e)+{\mathcalligra{w}}(e')\), we directly update \({\mathcalligra{w}}(e'')\) by \({\mathcalligra{w}}(e) +{\mathcalligra{w}}(e')\) and assign 1 to \({\textsf{cnt}} (e'')\). Meanwhile, \(e''\) is pushed into Q with \(\textsf{type}\) =‘dec’ (line 19–23). Finally, we update \({\mathcalligra{w}}(e)\) if \({\textsf{type}}\)=‘inc’ and invoke \(\textsf{KeepSCDom}\) algorithm (line 24–25). Note that, in line 14 of \(\textsf{KeepSCDom}\) algorithm, we omit the update for \({\mathcalligra{w}}(e')\) as it will be updated later in line 24 of \(\mathsf {CHLRMaintenance^*}\) algorithm. When all shortcuts in Q finish their update propagation, we obtain the new CHLR on \(G'\) correctly.

Example 5

Considering the road network G in Fig. 1a and CHLR on G shown in Fig. 1b, Fig. 3 shows the update process of Algorithm 4. Given the same updated edge \(e_o=((v_4,v_6),5,\{b\})\), and new weight 7 and new label \(\{c\}\) for \(e_o\), when process the child shortcuts of \(e_o\), compared with Algorithm 3, the update operation for \(e_1=((v_5,v_6),7,\{b\})\) is skipped as \({\textsf{cnt}} (e_1)=2\), Algorithm 4 just needs to decrease \({\textsf{cnt}} (e_1)\) by 1. Hence, Algorithm 4 can improve the efficiency of CHLR maintenance.

Theorem 3

Given a road network G and a changed edge e, the time complexity of \(\mathsf {CHLRMaintenance^*}\) algorithm to update CHLR index is \(O(|E_\Delta | \cdot log|E_\Delta | +|E_\Delta | \cdot d_{\textsf{max}})\), where \(E_\Delta\) denotes the changed shortcuts in CHLR.

Proof

In \(\mathsf {CHLRMaintenance^*}\) algorithm, only the changed shortcuts will be pushed into the priority queue Q. Q needs to sort shortcuts based on their update order which consumes \(O(|E_\Delta | \cdot log|E_\Delta |)\) time. Moreover, when update a shortcut \(e=(u,v)\) in Q, if \(\textsf{type}\) =‘dec’, e can be updated in O(1) time (line 22 of Algorithm 4), otherwise, if \({\textsf{cnt}} (e)<1\), we need to recompute the weight of e by visiting its parents which costs \(O(d_{\textsf{max}})\) time. Meanwhile, to keep the shortcut dominance, in the worst case, the weights of all shortcuts incident to (u, v) should be computed (line 6 of Algorithm 2) with \(O(d_{\textsf{max}})\) time. Therefore, the total time complexity of \(\mathsf {CHLRMaintenance^*}\) is \(O(|E_\Delta | \cdot log|E_\Delta | +|E_\Delta | \cdot d_{\textsf{max}})\). \(\square\)

On the real road network, the frequency of edge updates is high. Many edges may change in a very short period of time. When dealing with a large number of edge updates, a naive idea is to process them edge by edge through invoking \(\mathsf {CHLRMaintenance^*}\) algorithm. In this way, one shortcut may be updated multiple times due to different edge changes, which will lead to unnecessary time cost. Motivated by it, in this section, we propose a CHLR batch maintenance algorithm for batch update. The main thought is that build the hierarchy of edges/shortcuts by splitting them into multiple layers and update shortcuts in a bottom-up manner. Following the thought, all shortcuts will be only updated once when necessary. We first define the layer of edges as follows.

Definition 8

(Layer of Shortcut) Given a road network \(G'\) with CHLR, for each shortcut e in \(G'\), the layer number of e is denoted as Lay(e). \(Lay(e)=1\) if the child set of e is empty, otherwise \(Lay(e) = max\{Lay(e')\} + 1\), where \(e'\) is a child of e.

Example 6

For the road network G in Fig. 1a and the CHLR of G in Fig. 1b, Fig. 3 gives the neighborhood of shortcuts. By Definition 8, we find that shortcut \(((11,9), 7, \{a,b\})\) has no child, so its layer is 1, and the layer number of its parent \(((8, 9), 2, \{a\})\) is the maximum number of layers of all children plus 1, which is 2.

Lemma 4

For each shortcut layer l, shortcuts update on l only affect the shortcuts on the upper layers and have no effect on the shortcuts on the lower layers.

Proof

For each shortcut e, \(e'\) and \(e''\) are the parents of e. Based on Lemma 1, e will be only affected by its parents \(e'\) and \(e''\). By Definition 8, the layer of e is upper than that of \(e'\) and \(e''\). Hence, the lemma holds. \(\square\)

Lemma 5

Update shortcuts from lower layer to upper layer in a bottom-up manner, the correctness of this approach can be guaranteed.

Proof

Reconsidering the update process of \(\mathsf {CHLRMaintenance^*}\) algorithm, when each update is propagated, for each shortcut e, it must wait for all its parents to be updated before getting its new value. Based on Definition 8, all parents of e are on the lower layers; when update e, all its parents have already been updated. Hence, the correctness of our bottom-up approach can be guaranteed. \(\square\)

Example for batch update of \(\mathsf {CHLRMaintenance ^*}\)-\(\textsf{Batch}\) algorithm

Full size image

6.1 Algorithm \(\mathsf {CHLRMaintenance^*}\)-\(\textsf{Batch}\)

Following Lemma 5, given a set of changed edges U, we propose our batch index maintenance algorithm \(\mathsf {CHLRMaintenance^*}\)-\(\textsf{Batch}\). The pseudocode is shown in Algorithm 5. A bucket array B is used to store the shortcuts with different layers and initialized as \(\emptyset\) (line 1). Similar to Algorithm 4, we first update edges in U one by one (lines 2–11). Then, we process the shortcuts on the bucket corresponding to the largest layer first (line 12). For each shortcut e that has changed, the same update propagate chain is used; e’s child \(e''\) to be updated is deposited into \(B[Lay(e'')]\) (lines 15–27). Following Lemma 4, after a layer has been processed, the next layer is processed (line 28). When all layers are processed, the CHLR index is updated correctly.

Example 7

Considering the road network G shown in Fig. 1a, given two edge changes, edge ((1, 3), 2, \(\{a\})\) changes to \(((1,3), 1, \{c\})\) and \(((5,1), 6, \{b\})\) changes to \(((5,1), 5, \{c\})\); according to Definition 8, it can be found that Lay((1, 3), 2, \(\{a\})=3\) and \(Lay((5,1), 6, \{b\})=2\). Then according to Algorithm 5, shortcut \(((1,3), 2, \{a\})\) will be added into B[3] and \(((5,1), 6, \{b\})\) will be added into B[2]. According to Algorithm 5, the update process starts with shortcuts in B[3] and then move to upper layers. This update process is shown in Fig. 4. Compared with \(\mathsf {CHLRMaintenance^*}\) algorithm, the value of \(((5,9), \{b,c\})\) is recalculated twice due to the two edge changes. However, in Algorithm 5, the value of \(((5,9), \{b,c\})\) is only calculated once when processing B[1]. Thus, our Algorithm 5 can reduce unnecessary computations.

6.2 Vertex/Edge Deletion or Insertion

In this paper, we focus on the CHLR index maintenance for edge changes. However, our algorithms can also address the index maintenance for vertex/edge deletion or insertion. Specifically, when a new vertex v is inserted, we assign \(o_{{\textsf{max}}}\)+1 to v as its order where \(o_{{\textsf{max}}}\) is the largest order in G. Then, deleting/inserting a vertex is equivalent to deleting/inserting a series of edges, so we can just focus on the deleting/inserting edge scenario. When an edge \(e_1\) is deleted, it is equivalent to the weight of that edge being increased to infinity. Hence, the input of our Algorithm 5 is \(U=\{e_1=((u_1,v_1),w_o,l_o,\infty ,l_o)\}\) where \(w_o\) is \(e_1\)’s old weight and \(l_o\) is the label of \(e_1\). Then, our algorithm can update the index correctly. When an edge \(e_2\) is inserted with weight \(w_n\), it is equivalent to the weight of that edge being decreased from infinity to \(w_n\). Hence, we can update our index by invoking Algorithm 5 with \(U=\{e_2=((u_2,v_2),\infty ,l_n,w_n,l_n)\}\) where \(l_n\) is the label of \(e_2\).

6.3 Parallel Method

To further improve the efficiency of index maintenance, we propose a parallel method to update shortcuts in parallel based on the following lemma.

Lemma 6

For each shortcut e with layer l, updating e does not affect other shortcuts on the l-layer.

Proof

A shortcut change only affects its descendants via its children. When two shortcuts belong to the same layer, by Definition 8, they are not each other’s child or descendant, so they do not affect each other. \(\square\)

Based on Lemma 6, the order of updates within the same layer can be arbitrary. According to our batch index maintenance algorithm, combined with Lemma 6, they provide an opportunity to process shortcuts at the same layer in parallel. In this way, the efficiency of maintaining index can be obviously improved through distributing the processing of shortcuts on the same layer to multiple threads, and the specific implementation is given below.

We use OpenMP^{Footnote 1} for parallel computing. OpenMP is a multi-threaded programming solution for shared memory parallel systems. Serial code can be easily transformed into parallel execution with OpenMP. By simply adding #pragma instructions to the code, programs can be automatically processed in parallel, which greatly reduces the difficulty and complexity of parallel programming. Therefore, we rely on OpenMP to process updates of shortcuts within the same layer in parallel. Specifically, in Algorithm 5, the for loop starting at line 14 is used to process the updates of the shortcuts in the bucket with layer i, so the for loop can be run in parallel. Openmp parallel for assigns the computation load for different shortcuts on the same layer to multiple threads to achieve our parallel method for batch update.

Running time of different algorithms varying the percent of weight decrease

Full size image

Running time of different algorithms varying the percent of weight increase

Full size image

7.1 Datasets

We evaluate our algorithms on 8 real road networks, in which the weight of edges is the length of each road and the label shows the category of different roads. The datasets are downloaded from DIMACS.^{Footnote 2} Table 2 gives the statistic of datasets, where \(|\Sigma |\) is the number of labels and \(d_{\textsf{max}}\) represents the maximum degree of vertices in the corresponding augmented graphs. All the experiments are conducted on a machine with Xeon(R) Gold 6258R CPU 2.70GHz and 1TB RAM running Linux. The core number of CPUs is 32.

7.2 Algorithms

We compare the performance among these algorithms: (1) \(\textsf{Rebuild}\): the state-of-the-art algorithm to construct CHLR index [27]; (2) \(\textsf{Baseline}\): the \(\textsf{Baseline}\) approach proposed in Sect. 4; (3) \(\textsf{CHLRM}\): the \(\textsf{CHLRMaintenance}\) algorithm proposed in Sect. 5; (4) \(\mathsf {CHLRM^*}\): the algorithm \(\mathsf {CHLRMaintenance^*}\) with optimization strategy proposed in Sect. 5.5; (5) \(\mathsf {CHLRM^*}\)-\(\textsf{B}\): \(\mathsf {CHLRMaintenance^*}\)-\(\textsf{batch}\) algorithm proposed in Sect. 6.

For the vertex order in the road networks, we generate vertex order following the method used in [16, 27] with the same setting.

Running time of different algorithms varying the number of changed edges

Full size image

Hit rate of different algorithms varying the number of changed edges

Full size image

7.3 Exp-1: Efficiency of Algorithms When Varying the Percent of Weight Decrease/Increase

In this experiment, we evaluate the efficiency of \(\textsf{Baseline}\), \(\textsf{CHLRM}\) and \(\mathsf {CHLRM^*}\) with varying the percent of weight decrease/increase on all datasets. On each dataset, we randomly select 1000 edges as changed edges. We use \({\mathcal{W}_{o}}\) to denote the original weights of the changed edges. We first change edges’ labels and decrease their weights as \(20\%{{\mathcalligra{w}}_{o}}-80\%{\mathcal{W}_{o}}\). The running time of three algorithms with different percent of weight decrease is recorded in Fig. 5. Then, we increase their weights as \(120\% {\mathcal{W}_{o}}-200\% {{\mathcalligra{w}}_{o}}\). The corresponding running time is shown in Fig. 6.

On all datasets, \(\mathsf {CHLRM^*}\) and \(\textsf{CHLRM}\) can achieve up to 2 orders of magnitude speedup compared with \(\textsf{Baseline}\). It’s because that \(\textsf{Baseline}\) often performs the update for edges whose weights are not changed, which leads to unnecessary overhead of \(\textsf{Baseline}\). However, our \(\mathsf {CHLRM^*}\) and \(\textsf{CHLRM}\) can avoid the unnecessary overhead by a novel update propagate chain, in which only the changed shortcuts can further affect other shortcuts. For the efficiency of algorithms when varying the percent of weight increase, Fig. 6 shows similar phenomena with Fig. 5. \(\mathsf {CHLRM^*}\) is fastest among three algorithms. Furthermore, \(\mathsf {CHLRM^*}\) outperforms \(\textsf{CHLRM}\) on all datasets. It’s because \(\mathsf {CHLRM^*}\) utilizes the optimization strategy based on weight count, which can further avoid the invalid update. Moreover, the running time of algorithms changed with varying the percent of weight decrease/increase is inapparent, which demonstrates our algorithms have good scalability with the percent of weight change.

7.4 Exp-2: Efficiency of Algorithms When Varying the Number of Changed Edges

In this experiment, we compare the efficiency of \(\textsf{Rebuild}\), \(\textsf{Baseline}\), \(\textsf{CHLRM}\) and \(\mathsf {CHLRM^*}\) algorithms with changing \(0.1\% |E| -100\% |E|\) edges. The results are shown in Fig. 7.

As shown in Fig. 7, since \(\textsf{Rebuild}\) is the method to rebuild the CHLR index which directly reconstructs the index, the number of changed edges has negligible effect on the running time of \(\textsf{Rebuild}\), the running time of \(\textsf{Rebuild}\) is nearly unchanged. And the running time of \(\textsf{Baseline}\) increases when the number of changed edges increases. It’s because more shortcuts need to be updated. Moreover,\(\textsf{CHLRM}\) and \(\mathsf {CHLRM^*}\) are always faster than \(\textsf{Baseline}\). Compared with \(\textsf{Rebuild}\), \(\textsf{CHLRM}\) and \(\mathsf {CHLRM^*}\) spend less time updating the CHLR when 10% edges change. Meanwhile, when 100% edges are changed, the running time of \(\textsf{CHLRM}\) and \(\mathsf {CHLRM^*}\) is near to the time of rebuilding the CHLR by \(\textsf{Rebuild}\) algorithm. The experiment results indicate the significant efficiency of our \(\textsf{CHLRM}\) and \(\mathsf {CHLRM^*}\) algorithm.

Running time of \(\mathsf {CHLRM^*}\) and \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) varying the number of changed edges

Full size image

The speedup with the increasing thread number for parallel method

Full size image

7.5 Exp-3: Effectiveness of CHLR Maintenance Algorithms

In this experiment, we evaluate the effectiveness of different algorithms by comparing the hit rate of them. The hit rate is denoted as \(\frac{|E_\Delta |}{|E_U|}\), where \(E_\Delta\) denotes the shortcuts whose weights are changed and \(E_U\) denotes the shortcuts recomputed by algorithms.

As shown in Fig. 8, with the increasing of the number of changed edges, the hit rate of three algorithms increases as well because more shortcuts will be further changed. Besides, \(\textsf{CHLRM}\) performs better than \(\textsf{Baseline}\), \(\mathsf {CHLRM^*}\) achieves the highest hit rate among them on all update cases. It verifies that our \(\textsf{CHLRM}\) can avoid the unnecessary update compared with \(\textsf{Baseline}\), and \(\mathsf {CHLRM^*}\) can further reduce the invalid update benefitted from the optimization strategy, which also confirms the reasons for the efficiency of our optimized algorithm at Exp-1 and Exp-2.

7.6 Exp-4: Efficiency of \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) Algorithm for Batch Update

In this experiment, we compare the running time between \(\mathsf {CHLRM^*}\) algorithm and \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) algorithm with changing \(0.1\% |E| -100\% |E|\) edges. Figure 9 shows the results.

As shown in Fig. 9, \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) algorithm outperforms \(\mathsf {CHLRM^*}\) algorithm on all datasets. It’s because \(\mathsf {CHLRM^*}\) algorithm may update the shortcuts on the same layer multiple times due to different edge changes, which will introduce unnecessary time overhead. Meanwhile, the advantage of \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) is that the shortcuts are updated layer by layer, avoiding processing the same shortcut multiple times, which improves the efficiency of index maintenance. The running time gap between \(\mathsf {CHLRM^*}\) and \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) increases as the number of changed edges ranges from 0.1 to 10%. But when the number of changed edges is more than 10%, the running time gap may decrease such as Fig. 9c. This is because as the number of edges in the batch increases, the number of updated shortcuts also increases, which weakens the advantages of \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) against \(\mathsf {CHLRM^*}\). Even though, \(\mathsf {CHLRM^*}\)-\(\textsf{B}\) still outperforms \(\mathsf {CHLRM^*}\).

7.7 Exp-5: Speedup of Parallel Method When Varying the Number of Threads

In this experiment, we compare the speedup with different numbers of threads when running the parallel version of \(\mathsf {CHLRM^*}\)-\(\textsf{B}\). We record the speedup of running time compared with single thread with varying the number of threads. The results are shown in Fig. 10.

By observing the results, it demonstrates that the speedup of our proposed parallel method increases as the number of threads increases. It’s because that, benefited from our parallel method, the edges from the same layer can be updated in parallel. And, more threads will provide higher computational efficiency.

In this paper, we propose a novel CHLR maintenance algorithm, in which an update propagate chain is designed to propagate the shortcuts whose weights are actually changed without losing the accuracy guarantee. Moreover, an optimization strategy is presented to make sure that shortcuts are updated when necessary, it can further improve the efficiency of index maintenance. Considering the frequency of edge changes, we also propose a batch index maintenance algorithm to handle batch edge changes. Furthermore, a parallel method is proposed to further accelerate calculations. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the efficiency and effectiveness of our optimized algorithms which can achieve up to 2 orders of magnitude speedup compared with \(\textsf{Baseline}\). We also evaluate the efficiency of our batch index maintenance algorithm and parallel method.