# 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
); (ii) to find pairs of vertices \(u,v\) whose cover property can be broken in \(G^{\prime}\) due to removals of outdated entries, it suffices to determine vertices of \(F_{G}^{L}(x,y)\) and \(B_{G}^{L}(x,y)\),

Therefore, the strategy of algorithm clean is divided in two steps. First, it computes sets \(H_{f}(x,y)\) and \(H_{b}(x,y)\), according to the definition (line 1 of Algorithm 3), and then it performs two suited visits of the input graph \(G\) (Algorithms 5 and 6) with the two-fold aim of identifying the vertices of the two

Figure 5: (a): an example of the contradiction reached in the proof of Property 3. Suppose vertex ordering is \(\{x_{0},x_{1},x_{2},\ldots,x_{5}\}\) and all arcs weight 1 for the sake of the example. Therefore, in any minimal well-ordered 2-hop-cover labeling entry \((x_{1},\delta_{x_{4}x_{1}})\) cannot belong to \(L_{\mathrm{out}}(x_{4})\). This allows Algorithm clean to avoid removing correct entries. (b): a case where a correct entry is preserved by Algorithm clean. Suppose the vertex ordering is \(\{x_{0},x_{1},x_{2},\ldots,x_{7}\}\) and all arcs weight 1 for the sake of the example. Therefore in any minimal well-ordered 2-hop-cover labeling, \(L_{\mathrm{out}}(x_{4})\) will contain \((x_{0},\delta_{x_{4}x_{0}})\) with \(\delta_{x_{4}x_{0}}=d(x_{4},x_{0})=4\). Clearly, also \(L_{\mathrm{out}}(x_{1})\) and \(L_{\mathrm{out}}(x_{2})\) will contain. similarly, entries \((x_{0},3)\) and \((x_{0},3)\), respectively. If arc \((x_{2},x_{5})\) undergoes some decremental update, the (correct) entry in \(L_{\mathrm{out}}(x_{4})\) is not removed thanks to the presence of the alternative shortest path through \(x_{1}\) with the same weight as that through \(x_{2}\). cover graphs and removing outdated entries. These two sets are stored to evaluate, in a subsequent phase, whether the cover property in the new graph is satisfied or not. ```
Input: Graph G, 2-hop-cover labeling L of G, \(\operatorname{arc}(x,y)\) subject to decremental update. Output: Resulting graph G', a labeling L' containing only correct label entries for G' (but possibly not covering it). 1 Compute H\({}_{\texttt{f}}(x,y)\) and H\({}_{\texttt{b}}(x,y)\);
2(o_removal,OUT) \(\leftarrow\)\(\textsc{fclean}(G,\operatorname{L},x,y,H_{\texttt{b}}(x,y))\);
3(i_removal,IN) \(\leftarrow\)\(\textsc{bclean}(G,\operatorname{L},x,y,H_{\texttt{f}}(x,y))\);
4 Apply update to \(\operatorname{arc}(x,y)\) to obtain G';
5L' \(\leftarrow\) L;
6 foreachv \(\in\) OUT do /* Remove outdated entries from outgoing labels */
7 foreachh \(\in\) o_removal do Remove \((\texttt{h},*)\) from \(\operatorname{L}^{\prime}_{\texttt{out}}(v)\);
8 foreachv \(\in\) IN do /* Remove outdated entries from incoming labels */
9 foreachh \(\in\) i_removal do Remove \((\texttt{h},*)\) from \(\operatorname{L}^{\prime}_{\texttt{in}}(v)\);
10 return\((G^{\prime},\operatorname{L}^{\prime},\operatorname{OUT},\operatorname{IN})\)
```

**Algorithm 3**Algorithm clean

Specifically, each of the two visits start from the endpoints of the arc that is interested by the update (x and y, respectively), as shown in Algorithms 5 and 6, and proceed by determining vertices of the cover graphs on the basis of the corresponding conditions (see Definitions 1 and 2). To limit the search to such vertices only, each visit employs a priority queue to drive the exploration in a shortest-path first fashion, starting from either x or y, and performs corresponding relax operations (see procedure 7 used in both Algorithms 5 and 6). This guarantees that vertices of the cover graphs are analyzed in order of distance from x or y and hence that entries are removed only if outdated. In fact, whenever a vertex v of the forward (backward, resp.) cover graph is found, its outgoing (incoming, resp.) label is searched for entries in the form \((\texttt{h},*)\) for every \(\texttt{h}\in H_{\texttt{b}}(x,y)\) (\(\texttt{h}\in H_{\texttt{f}}(x,y)\), resp.). If any entry of this kind is present, then the algorithm determines whether the entry is correct or not for G' by looking at the outgoing (incoming, resp.)