# 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
neighbors' labels to establish whether there exists a second shortest path in G from v to h (from h to v, resp. ), which is sufficient for the label entry to be correct in G' (see Figure 4(b)). If the search fails, then the entry is outdated and hence it is selected for removal (see line 12 of Algorithm 5 and line 12 of Algorithm 6) by adding the hub to a corresponding list (one per vertex, see line 17 of Algorithm 5 and line 17 of Algorithm 6). Otherwise, it is correct and hence it is preserved (see, e.g., line 13 of Algorithm 5). Once all vertices of the cover graphs have been found, and their label sets searched to select outdated entries, the visit terminates and both the lists of hubs corresponding to outdated entries and sets of vertices of the cover graphs are returned. ```
Input: Graph \(G^{\prime}\), Labeling \(L^{\prime}\), sets \(OUT\) and IN Output: 2-hop-cover labeling \(L^{\prime\prime}\) of \(G^{\prime}\)
1 foreach\(h\in\{IN\cup OUT\}\) in ascending order of \(IDX(h)\)do
2\(Q\leftarrow\emptyset\);
3\(L^{\prime\prime}\leftarrow L^{\prime}\);
4 if\(h\in IN\)then
5 foreach\(s\in OUT\,:\,s>h\)do /* \(s<h\Longrightarrow h\) cannot be added to \(L_{out}(s)\) */
6\(\delta_{min}\leftarrow\infty\);
7 foreach\(v_{i}\in N_{out}(s)\,:\,v_{i}\
ot\in OUT\)do
8 if\(h<v_{i}\)and\((h,\delta_{v_{i}t})\in L^{\prime\prime}_{out}(v_{i})\)then
9\(\delta_{min}\leftarrow\min\{\delta_{min},\delta_{v_{i}t}\}\);
10\(\text{mark}[s]\leftarrow\text{true}\);
11\(Q.Insert(\langle s,\delta_{min}\rangle)\);
12 while\(Q\
eq\emptyset\)do
13\((v,\delta)\leftarrow Q.deleteMin()\);
14 if\(\delta<PQ(v,h,L^{\prime\prime},IDX(h))\)then
15\(L^{\prime\prime}_{out}(v)\leftarrow L^{\prime\prime}_{out}(v)\cup\{(h,\delta)\}\);
16\(\text{prunedRelax}(v,N_{in}(u),\text{true},OUT)\);
17 if\(h\in OUT\)then
18 foreach\(t\in IN\,:\,t>h\)do /* \(t<h\Longrightarrow h\) cannot be added to \(L_{in}(t)\) */
19\(\delta_{min}\leftarrow\infty\);
20 foreach\(v_{i}\in N_{in}(t)\,:\,v_{i}\
ot\in IN\)do
21 if\(h<v_{i}\)and\((h,\delta_{v_{i}h})\in L^{\prime\prime}_{in}(v_{i})\)then
22\(\delta_{min}\leftarrow\min\{\delta_{min},\delta_{v_{i}h}\}\);
23\(\text{mark}[t]\leftarrow\text{true}\);
24\(Q.Insert(\langle t,\delta_{min}\rangle)\);
25 while\(Q\
eq\emptyset\)do
26\((v,\delta)\leftarrow Q.deleteMin()\);
27 if\(\delta<PQ(h,v,L^{\prime\prime},IDX(h))\)then
28\(L^{\prime\prime}_{in}(v)\leftarrow L^{\prime\prime}_{in}(v)\cup(h,\delta)\);
29\(\text{prunedRelax}(v,N_{out}(u),\text{false},IN)\);
```

**Algorithm 4**Algorithm recover

The actual removal of outdated entries is performed then at this point, once the two visits are concluded, by sequentially scanning only the labels of vertices of the cover graphs that contain at least one outdated label entry (see lines 7-9 of Algorithm 3). This is done for the sake of the efficiency, so to be able to test the membership of vertices of the cover graph and the presence of outdated entries in linear time, by exploiting the content of the 2-hop-cover labeling \(L\) of \(G\) (see, e.g., line 18 of Algorithm 5 or line 18 of Algorithm 6). The naive alternative to achieve the same purpose would be executing a traditional shortest-path algorithm (with possibly superlinear worst-case running time, e.g., [PERSON]'s). We conclude the section by proving some results concerned with the correctness of Algorithm clean. In particular, first we show the two sets \(OUT\) and IN, computed by the algorithm, are exactly the two vertex sets of \(F^{L}_{G}(x,y)\) and \(B^{L}_{G}(x,y)\). ```
Input: Graph G, 2-hop-cover labeling L of G, \(\operatorname{arc}\left(x,y\right)\) subject to update, set \(\operatorname{H}_{\texttt{f}}(x,y)\). Output: Set o_removal of entries to remove from outgoing labels, set UUT.