# 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  
The new method is inspired by some empirical observations on the behavior of bidir-2 hc, the only previously known solution for updating 2-hop-cover labelings against decremental graph changes. These observations come from a preliminary experimental study we conducted through profiling software on an implementation of bidir-2 hc itself. Specifically, our data show that:  
1. the first two phases require typically small fractions of the time taken by bidir-2 hc, even in very large instances. However, some \"computational redundancy\" is observed. In particular, there can be some vertices whose label sets do not contain any outdated entry and yet such sets are scanned twice, once during the detection phase and once during the removal phase (within the computed set of _affected vertices_, see [26] or Section 2.2). This is clearly an undesired behavior that we aim at removing by designing a new algorithm for the purpose. An example of this scenario is shown in Figure 2.  
2. the largest fraction of the entire computational effort to update a labeling, as a consequence of a decremental update, is spent by bidir-2 hc on testing whether the cover property is satisfied and in restoring it when it is not, i.e., on the third phase. During this step, a number of shortest-path driven visits of the graph is performed, each rooted at one of the mentioned affected vertices and pruned according to a policy that is similar to that of fs-2 hc. Unfortunately, however, the pruning conditions are less restrictive with respect to those of fs-2 hc. Specifically, during the search started at \(v_{k}\), whenever a vertex \(u\) is settled with a distance of \(\delta\), the algorithm checks whether \(Q(v_{k},u,L^{k-1})\leqslant\delta\) and prunes the search in the affirmative case, since this implies that labeling \(L^{k-1}\) contains a hub vertex for \((v_{k},u)\) and for all pairs \((v_{k},x)\) such that there exists a shortest path between \(v_{k}\) and \(x\) passing through node \(u\). On the contrary, bidir-2 hc must consider the fact that new paths, connecting pairs of affected vertices, can pass through non-affected vertices. Hence, to guarantee that the cover property is restored for all pairs of vertices, the search is pruned only if \(Q(v_{k},u,L^{k-1})\leqslant\delta\)_and_\(u\) is affected. A consequence of this strategy is that many vertices of the graph, whose label sets do not change, are visited and tested for pruning by the searches of the third phase. This is, again, an undesired behavior we aim at avoiding by our new solution. Beyond the Limitations of bidir-2 hc. Our algorithm tries to overcome the above-mentioned limitations by attacking the problem in a different way with respect to bidir-2 hc. In details, the algorithm works in two phases, named clean and recover, respectively, as summarized in Algorithm 2. The aim of the clean phase is two-fold: (i) that of identifying and removing outdated label entries efficiently from the labeling (to produce an updated version of the labeling that contains **only entries** that are **correct** for the new graph); (ii) that of determining pairs of vertices that remain uncovered by the removal of outdated label entries without scanning their label sets twice (as done by bidir-2 hc). The recover phase's purpose, instead, is that of restoring the cover property for such pairs by suitably adding new label entries without visiting vertices of the graph whose label sets are unchanged by the graph update (unlike bidir-2 hc). The two phases are described in the following sections. ```
Input: Graph G, 2-hop-cover labeling L of G, \(\operatorname{arc}\left(x,y\right)\) subject to decremental update. Output: Resulting graph G', 2-hop-cover labeling L' of G'.