# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 2 Notation and Background
### 2-hop-cover Labeling  
In this section, we summarize the main characteristics of the 2-hop-cover labeling method. Our descriptions refer to the most general case of weighted directed graphs, which is the most complex to handle. Simpler versions of the approaches can be obtained for unweighted or undirected graphs, we refer the reader to [26] for a thorough discussion on the differences. For each vertex \(v\) of \(G\), we call _incoming_ and _outgoing labels_, respectively, \(L_{in}(v)\) and \(L_{out}(v)\) of \(v\) two sets of pairs (also known as _label entries_) of the form \((u,\delta_{uv})\) and \((u,\delta_{vu})\), respectively, where \(u\in V\) while \(\delta_{uv}=d_{G}(u,v)\) and \(\delta_{vu}=d_{G}(v,u)\), respectively. The collection of all the labels \(L=\langle[L_{out}(v)]_{v\in V},[L_{in}(v)]_{v\in V}\rangle\) is referred to as a _distance labeling_ of \(G\). For the sake of readability, we use \(u\in L_{out}(v)\) (\(u\in L_{in}(v)\), respectively) to denote that \((u,\delta_{vu})\in L_{out}(v)\) (\((u,\delta_{uv})\in L_{in}(v)\), respectively), whenever the meaning is clear from the context. Similarly, for any \(u,v\in V\) we say \(L_{out}(u)\cap L_{in}(v)\
eq\emptyset\) whenever there exists some \(h\in V\) such that \((h,\delta_{uh})\in L_{out}(u)\) and \((h,\delta_{hv})\in L_{in}(v)\) (and vice versa). Labels can be used to retrieve the (exact or approximate) distance from vertex \(s\in V\) to vertex \(t\in V\) in \(G\) by performing a _query on the distance_ from \(s\) to \(t\), as in Equation (1). \[Q(s,t,L)= \begin{cases}\min_{v\in V}(\delta_{sv}+\delta_{vt}\,|\,(v,\delta_{sv} )\in L_{out}(s)\wedge(v,\delta_{vt})\in L_{in}(t))&\text{if }L_{out}(s)\cap L_{in}(t)\
eq\emptyset\\ \infty&\text{otherwise.}\end{cases}  \tag{1}\]  
Please note that each query requires access to the labels of \(s\) and \(t\) only. A distance labeling \(L\) is a 2-hop-cover _labeling_[18] of a graph \(G\) (often referred to simply as labeling of \(G\) in the remainder of the paper) if, for any pair of vertices \(s,t\in V\):  
* either \(L_{out}(s)\cap L_{in}(t)\
eq\emptyset\) contains (at least) a vertex \(h\in V\) lying on a shortest path between \(s\) and \(t\) in \(G\), and therefore \(Q(s,t,L)=\delta_{sh}+\delta_{ht}=d_{G}(s,t)\) (\(s\) and \(t\) are connected in \(G\));
* or \(L_{out}(s)\cap L_{in}(t)=\emptyset\) and hence \(Q(s,t,L)=d_{G}(s,t)=\infty\) (when \(s\) and \(t\) are not connected in \(G\)). If a pair of vertices \((s,t)\) is connected, then the above-mentioned vertex \(h\in L_{out}(s)\cap L_{in}(t)\), lying on a shortest path from \(s\) to \(t\), is called _lub vertex_ of pair \(s,t\) (or simply _lub_). Vertex \(h\) is said to _cover_ pair \(s,t\). Symmetrically, the pair is said to be _covered_ by \(h\) and, thus, by the labeling \(L\). By extension, if the above conditions hold, the graph is said to be _covered_ by the labeling and the labeling is said to _cover_ the graph (or to satisfy the _cover property_ for the considered graph). Notice that a given pair of vertices \(u,v\in V\) can be covered by more than one hub vertex, depending on how the 2-hop-cover labeling is computed. A naive approach to compute a 2-hop-cover labeling of a graph consists of executing twice a shortest-path algorithm that can be a Breadth First Search (BFS) in unweighted graphs or the [PERSON]'s algorithm in weighted ones, using as root each vertex \(v\in V\), once _forward_ (that is, in \(G\)), and once _backward_ (that is, in \(G^{T}\)). In the forward case, when a vertex \(u\) is extracted from the queue, used by the shortest-path algorithm, with a priority of \(d\), that is when a shortest path with weight \(d\) from the root \(v\) to \(u\) in \(G\) is found, then entry \((u,\delta_{vu}=d)\) is added to \(L_{in}(u)\). In the backward case, instead, entry \((u,\delta_{uv}=d)\) is added to \(L_{out}(u)\) whenever vertex \(u\) is extracted from the queue and hence when a shortest path, with weight \(d\), from the root \(v\) to \(u\) in \(G^{T}\), is found.