# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 2 Notation and Background
### Dynamic Algorithms for Updating 2-hop-cover Labelings
\begin{split} PQ(s,t,L,k)=\begin{cases}\min_{v_{i}\in V,\delta_{v \in K}}\{\delta_{sv_{i}}+\delta_{v_{i}t}\,|\,(v,\delta_{sv_{i}})\in L_{out}(s) \wedge(v,\delta_{v_{i}t})\in L_{in}(t)\}&\text{if }L_{out}(s)\cap L_{in}(t)\
eq\emptyset\\ \infty&\text{otherwise.}\end{cases}\end{split}  \tag{2}\]  
In simpler terms, \(PQ(s,t,L,k)\) is the answer to a query from \(s\) to \(t\) computed from labeling \(L\) using distances to vertices \(v_{1},v_{2},\ldots,v_{k}\) only. Suppose now a resumed forward (backward, respectively) visit, originally rooted at \(v_{k}\) visits vertex \(u\) with distance \(\delta\), then it is possible to prune the search at \(u\) if \(PQ(v_{k},u,L,k)\leqslant\delta\) (\(PQ(u,v_{k},L,k)\leqslant\delta\), respectively). It can be shown that to obtain a 2-hop-cover labeling \(L^{\prime}\) of \(G^{\prime}\) by updating \(L\) with the above strategy, it suffices to resume forward and backward shortest-path searches rooted at vertices \(\{w:w\in L_{out}(a)\lor w\in L_{in}(b)\}\)[8]. **Algorithm** bidir-2 hc. First of all, notice that when handling a decremental graph update, outdated label entries must be removed from \(L\) to obtain a 2-hop-cover labeling \(L^{\prime}\) of \(G^{\prime}\), as otherwise it iseasy to show the cover property does not hold for \(G^{\prime}\). Specifically, even after a single decremental operation, a query on such labeling might return an arbitrary underestimation of the true value of distance in \(G^{\prime}\). For this reason, algorithm bidir-2 hc works in three phases. If we assume that an arc \((x,y)\) undergoes a decremental update (i.e., either it is removed or its weight is increased), in a first phase bidir-2 hc performs two shortest-path-like searches of the graph \(G\), one backward (i.e., on \(G^{T}\)) and one forward (i.e., on \(G\) itself), rooted at \(x\) and \(y\) respectively. By exploiting both \(L\) and the structure of the graph, the visits detect the so-called _affected vertices_, i.e., vertices that are candidate to contain at least one outdated label entry. In a second phase, the algorithm scans all such vertices and removes outdated label entries. For efficiency purposes, affected vertices are divided into two sets and are sorted according to the original vertex ordering, and the removal policy works as follows: (i) given an affected vertex \(v\) of the first set, entries \((u,\delta_{vu}\) such that \(u\) is in the second set are removed from \(L_{out}(v)\) (if any); (ii) given an affected vertex \(v\) of the second set, entries \((u,\delta_{uv}\) such that \(u\) is in the second set are removed from \(L_{in}(v)\) (if any). The result of the removal phase is that there might be pairs of affected vertices that are not covered by the resulting labeling, depending on the structure of \(G^{\prime}\). Therefore, a third phase to restore the cover property for all such pairs is executed to obtain a labeling \(L^{\prime}\) that covers \(G^{\prime}\). To this aim, a set of shortest-path searches is performed, namely one forward search in \(G^{\prime}\), rooted at each affected vertex of the first set, and one backward search in \(G^{\prime T}\), rooted at each affected vertex of the second set, following the vertex ordering to achieve both the well-ordered property and the minimality. Such visits essentially discover shortest paths connecting pairs of affected vertices and, accordingly, add entries to the corresponding labels. As well as both fs-2 hc and resume-2 hc, a pruning mechanism is incorporated in these visits, based on the ordering of vertices and on results of queries. However, the pruning is less \"aggressive\" and hence less effective in reducing the search space in practice. The motivation is essentially that shortest paths, connecting affected vertices in \(G^{\prime}\) or \(G^{\prime T}\), can pass through non-affected vertices (see [27; 29] for more details).