# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### Profiling of Algorithm bidir-2 hc
However, if arc \((\mathtt{x}_{1},\mathtt{x}_{0})\) is removed then \(\mathsf{d}_{\mathsf{G}}(\mathtt{x}_{4},\mathtt{x}_{0})\) changes while \(\mathsf{d}_{\mathsf{G}}(\mathtt{x}_{3},\mathtt{x}_{0})\) does not, since \(\mathtt{x}_{3}\) has two shortest paths of the same weight to \(\mathtt{x}_{0}\). (b): In the toy graph \(\mathsf{G}\) shown here the only shortest path from \(\mathtt{x}\) to \(\mathtt{h}\) passes through arc \((\mathtt{x},\mathtt{y})\). Therefore, if \((\mathtt{x},\mathtt{y})\) undergoes a decremental update, we have that \(\mathtt{x},\mathtt{x}_{1}\), and all vertices that are connected to \(\mathtt{x}_{1}\), are in the forward cover graph (in blue). Symmetrically, \(\mathtt{r}\) and \(\mathtt{h}\) are in the backward cover graph (in red) while \(\mathtt{k}_{1}\) and \(\mathtt{k}_{2}\) are in neither of the two cover graphs. Proof. : Consider that for any pair \(u,v\in V\), since \(L\) is a 2-hop-cover labeling, we have \(Q(u,v,L)=d_{G}(u,v)\). Moreover, having \(u\
ot\in F^{L}_{G}(x,y)\) and \(v\
ot\in B^{L}_{G}(x,y)\) implies both \(L_{out}(u)\) and \(L_{in}(v)\) contain only correct entries for \(G^{\prime}\). Therefore \(Q(u,v,L)=d_{G}(u,v)=d_{G^{\prime}}(u,v)\). Hence, regardless of the magnitude of the change on \((x,y)\), we are sure that the cover property is satisfied by \(L\) also in \(G^{\prime}\), for pairs \(u,v\) such that \(u\
ot\in F^{L}_{G}(x,y)\) and \(v\
ot\in B^{L}_{G}(x,y)\) and we do not need to search for outdated entries in outgoing labels of vertices of the forward cover graph nor in incoming labels of vertices of the backward cover graph. Now, we establish how to determine which entries are outdated in the labels of the vertices of the two cover graphs. Please note that there can be labels of vertices of the two cover graphs that do not contain outdated entries. Still, we will show it is necessary to identify such vertices since they might be interested by violations of the cover property due to the removals of the above-mentioned outdated entries. This heavily depends on the structure of the shortest paths in the graph and on the effect of the decremental update on such structure, as shown in the example of Figure 4.

**Property 3**. : _Let \(F^{L}_{G}(x,y)\) and \(B^{L}_{G}(x,y)\) be the forward and backward cover graphs, respectively. Let \(L\) be a well-ordered 2-hop-cover labeling of \(G\). Assume \(arc(x,y)\) is subject to a decremental operation and let \(G^{\prime}\) be the graph obtained by applying to \(G\) such modification. Let \(H_{\ell}(x,y)\subseteq V\) and \(H_{b}(x,y)\subseteq V\) be the sets of forward and backward invalid hubs. Then:_

1. _a label entry_ \((h,\delta_{vh})\) _in the outgoing label_ \(L_{out}(v)\) _of a vertex_ \(v\in F^{L}_{G}(x,y)\) _is outdated if and only if_ \(h\in H_{b}(x,y)\) _and there is no vertex_ \(u\in N_{out}(v)\) _such that: (i)_ \((h,\delta_{uh})\in L_{out}(u)\)_; (ii)_ \(w(v,u)+\delta_{uh}=\delta_{vh}\)_; (iii)_ \(u\
ot\in F^{L}_{G}(x,y)\)_;_
2. _a label entry_ \((h,\delta_{hv})\) _in the incoming label_ \(L_{in}(v)\) _of a vertex_ \(v\in B^{L}_{G}(x,y)\) _is outdated if and only if_ \(h\in H_{\ell}(x,y)\) _and there is no vertex_ \(u\in N_{in}(v)\) _such that: (i)_ \((h,\delta_{hu})\in L_{in}(u)\)_; (ii)_ \(w(u,v)+\delta_{hu}=\delta_{hv}\)_; (iii)_ \(u\
ot\in B^{L}_{G}(x,y)\)_._

Proof. : We focus on case 1. The proof for case 2 is symmetric. (\(\Rightarrow\)) First of all observe that if \(L_{out}(v)\) contains an outdated label entry \((h,\delta_{vh})\) then, by Lemma 2, we must have \(v\in F^{L}_{G}(x,y)\) and hence we know that \(d_{G}(v,h)=d_{G}(v,x)+w(x,y)+d_{G}(y,h)\) and \(\delta_{vh}=d_{G}(v,h)\
eq d_{G}(v,h)\), i.e., \(v\) is connected in \(G\) to \(y\) via a shortest path that includes \((x,y)\). By contradiction, we now assume that \((h,\delta_{vh})\) is outdated but one of the two following conditions is true:

1. \(h\
ot\in H_{b}(x,y)\);
2.