# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 2 Notation and Background
### Dynamic Algorithms for Updating 2-hop-cover Labelings  
Essentially, the only two known methods for updating 2-hop-cover labelings are those in [8; 26], named resume-2 hc and bidir-2 hc in what follows, respectively, whose main features are briefly summarized below, since the new approach we propose in this paper borrows some features from both solutions. We refer the reader to [8; 26] for a thorough description of the resume-2 hc and bidir-2 hc, respectively. **Algorithm** resume-2 hc. Given a graph \(G=(V,A)\) and a 2-hop-cover labeling \(L\) of \(G\), algorithm resume-2 hc is able to update \(L\) in order to reflect an incremental update (i.e., a newly added arc \((a,b)\
ot\in A\) or a decrease in the weight \(w(a,b)\) of an arc \((a,b)\in A\)). In particular, if we denote by \(G\) a graph before a given incremental modification, by \(L\) a 2-hop-cover labeling \(L\) of \(G\), and by \(G^{\prime}\) the graph resulting by the application of the change to \(G\), then resume-2 hc computes a 2-hop-cover labeling \(L^{\prime}\) of \(G^{\prime}\) by updating \(L\) as follows. First of all notice that resume-2 hc does not remove from \(L\) the so-called _outdated label entries_ of \(L\), i.e., entries in the label sets that correspond to shortest paths in \(G\) but not in \(G^{\prime}\), due to the incremental update occurred on arc \((a,b)\), and hence they are present also in \(L^{\prime}\). Formally, an _outdated entry_ is a pair \((u,\delta_{uv})\in L_{in}(v)\) (or symmetrically \((u,\delta_{vu})\in L_{out}(v)\)), for some \(u\) and \(v\) in \(G\), such that \(\delta_{uv}=d_{G}(u,v)\
eq d_{G^{\prime}}(u,v)\) (or symmetrically \(\delta_{vu}=d_{G}(v,u)\
eq d_{G^{\prime}}(v,u)\)). The above choice is motivated by the fact that distances can only decrease as a consequence of incremental updates and hence, if one adds entries corresponding to new shortest paths, then queries return correct distances in \(G^{\prime}\) for all pairs of vertices even in the presence of such outdated entries (i.e., the cover property is preserved). This is because the query algorithm searches for minimum values in the label sets. Therefore, resume-2 hc simply adds new label entries or overwrite distances of existing ones. A drawback of this approach is that the minimality of the resulting labeling \(L^{\prime}\) as a whole is broken even after a single update and this is known to affect the performance over time (periodical reprocessing is necessary to restore minimality and avoid the labeling grows too large). Observe that the problem of designing an incremental algorithm that does not suffer from this issue is still open [29]. The strategy of resume-2 hc, for adding label entries corresponding to new shortest paths, is based on the following two facts: (i) if the distance from a vertex \(v_{k}\) to a vertex \(u\) changes, then all new shortest paths from \(v_{k}\) to \(u\) pass through the updated arc \((a,b)\); (ii) if a shortest path \(P\) from \(v_{k}\) to \(u\
eq a,b\) changes, then the distance between \(v_{k}\) and \(w\) changes, where \(w\) is the penultimate vertex in \(P\). Based on the above insights, for every vertex \(v_{k}\), the idea is that it suffices to resume forward and backward, respectively, shortest-path visits (i.e., in \(G^{\prime}\) and \(G^{\prime T}\), respectively) that: (i) are originally rooted at \(v_{k}\); (ii) start at \(b\) and \(a\), respectively; (iii) stop at unchanged vertices. That is, instead of inserting \((v_{k},0)\) into the priority queue, the algorithm inserts pair \((b,d_{G}(v_{k},a)+w(a,b))\) (\((a,d_{G}(b,v_{k})+w(a,b))\), respectively). Then, the search proceeds by adopting a pruning mechanism similar to that of fs-2 hc described above, modified to consider that outdated entries are not removed. In particular, it employs the notion of _prefiral query_, denoted as \(PQ\), that, given two vertices \(s,t\) and an integer \(k\) and a labeling \(L\), is computed as in Equation (2). \[