# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 2 Notation and Background
### 2-hop-cover Labeling
It is easy to see how a labeling obtained as above covers the graph [7], since there is at least one hub vertex per pair of vertices (the root vertex of each visit). However, computing a labeling \(L\) as above costs \(\Theta(n\cdot SP(n,m))\) worst-case time, where \(SP(n,m)\) is the worst-case computational time of a corresponding shortest-path algorithm. Moreover, \(L\) contains \(\Theta(n^{2})\) hub vertices and hence \(\Theta(n^{2})\) label entries, which is the same space complexity of storing all pairs distances. Furthermore, it induces a query algorithm with \(\Omega(n)\) computational effort, since all labels contain \(\Theta(n)\) entries. Thus, this basic version of 2-hop-cover labeling is far from being considered an effective approach for distance mining, since, as is, it is worse than standard methods for shortest paths. To make it practical, one must aim at minimizing both running times for computing a labeling (a.k.a. _preprocessing times_) and _labeling size_ (i.e., total number of entries), which in turn hopefully induces small query times in practice. To this end, unfortunately, it is known that finding a minimum-size labeling covering a graph \(G\) is an NP-hard problem [18]. However, few heuristic approximation algorithms for computing compact labelings are known [3; 7; 18]. In particular, the ones in [3; 7] have been shown to achieve considerably better scalability, in terms of both preprocessing times and space requirements, than other methods in essentially all classes of graphs. Both these methods require \(\Theta(n\cdot SP(n,m))\) worst-case running time to compute a labeling that can have \(O(n^{2})\) label entries. Nevertheless, extensive experimentation shows they behave very well in practice. Specifically, they exhibit preprocessing times in the order of hours even for massively sized inputs, and produce labelings that have a labeling size that on average, is much smaller than the worst-case estimation of a constant multiple of \(n^{2}\)[3; 7]. This leads to have average query times that in practice, are below milliseconds even for the largest instances. The elements that are common to the two strategies are: (i) considering the vertices of \(V\) in order according to some importance criterion with respect to the shortest paths in the graph; (ii) performing a number \(n\) of shortest-path visits, each rooted at a vertex \(v_{i}\in V\) in the above-mentioned order, say \(\{v_{1},v_{2},\ldots,v_{n}\}\), that incrementally build the labeling starting from empty label sets (Observe that the ordering can be greedily changed in this phase to achieve better results); (iii) employing a so-called _pruning mechanism_ that stops the branch of the graph that is currently being explored whenever a _pruning condition_ is met. In particular, let us denote by \(\{v_{1},v_{2},\ldots,v_{n}\}\) the vertex ordering and by \(L^{k-1}\) the labeling computed after the execution of the two shortest-path visits, rooted at vertex \(v_{k-1}\) (i.e., containing only entries of the form \((v_{i},*)\) for \(v_{i}\leqslant v_{k-1}\)). If we consider a vertex \(u\) that is reached during the forward (backward, respectively) visit rooted at \(v_{k}\) and assume that \(\delta\) is the currently discovered distance from \(v_{k}\) to \(u\) (from \(u\) to \(v_{k}\), respectively). Then, the algorithm checks whether \(Q(v_{k},u,L^{k-1})\leqslant\delta\) (\(Q(u,v_{k},L^{k-1})\leqslant\delta\), respectively). If the above condition holds, then \(L^{k-1}\) already contains a hub vertex for pair \((v_{k},u)\) (\((u,v_{k})\), respectively) and for all pairs \((v_{k},x)\) such that there exists a shortest path between \(v_{k}\) and \(x\) passing through vertex \(u\) (for all pairs \((x,v_{k})\) such that there exists a shortest path from \(x\) to \(v_{k}\) passing through vertex \(u\), respectively). Therefore, the visit rooted \(v_{k}\) is _pruned_ at \(u\). Otherwise, the algorithm updates either \(L_{in}(u)\) or \(L_{out}(u))\) as described above and continues.