# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 1 Introduction  
Mining shortest-path distances is universally considered one of the most fundamental operation to be performed on graph data, due to the wide range of applications it finds. Prominent examples include social networks analysis [1], route planning [2, 3], intelligent transport systems [4], context-aware search [5, 6], web search optimization [7], graph databases [8, 9], decision making [10], analysis of biological networks [11], artificial intelligence [12] and network design [13]. Standard algorithms for solving the problem of computing answers to _queries on the distance_, i.e., to retrieve the weight of a shortest path between a pair of vertices of a given graph upon request, are well known and include the Breadth First Search (BFS) algorithm for unweighted graphs andthe [PERSON]'s algorithm for weighted ones. Unfortunately, there exists vast, mostly experimental, algorithmic literature showing they are not suited for solving the problem at large-scale, i.e., when the graph to be managed is massively sized [14; 15; 16; 17]. In fact, in these cases, the mentioned approaches do not scale well enough against the input' size, since their linear (or slightly superlinear for weighted graphs) worst-case time complexity yield impractical average time per query when graphs are huge (with up to millions of vertices and billions of arcs). The other extreme approach is to compute distances between all pairs of vertices beforehand and store them in an index [7]. Though in this way we can answer distance queries almost instantly, this approach is also unacceptable since preprocessing time and index size are quadratic and unrealistically large. For the above reasons, and since big graphs are becoming the norm in most modern application contexts that rely on distance mining, many smarter and more scalable techniques, between these two extreme solutions, have been proposed in the recent past to deal with massive graphs. Essentially all of them adopt the common strategy of preprocessing the graph to compute some data structure that is then exploited to accelerate the query algorithm [2; 3; 7; 18; 19; 20; 21; 22; 23]. Some of these methods have been designed to handle special classes of graphs, of interest of specific applications (e.g., speed-up techniques for route planning) and in road/transport networks (e.g., [2; 14; 20; 21; 24; 25]) while some others are general and provide speedups over baseline strategies regardless of the structural properties of the graph to be managed (e.g., [3; 15; 19; 23]). In this latter category we find 2-hop-cover-based labeling approaches that currently are considered state-of-the-art methods for distance mining in massive graphs. In fact, they have been shown to exhibit superior performance in terms of query times, allowing computation of shortest-path distances in microseconds even for billion-vertex graphs, at the price of a competitive preprocessing time and space overhead [7; 8; 21; 26; 27]. Specifically, such approaches rely on the idea of precomputing a compressed representation of the transitive closure of the input graph in terms of _concatenations of shortest paths_: for each pair of vertices of the input graph, such representation includes (at least) one intermediate vertex, called _hub vertex_, and (at least) two corresponding shortest paths, connecting the hub vertex to the two vertices of the pair, called _hops_. In this way, the shortest path connecting the pair of vertices can be reconstructed as the concatenation of the two hops at the hub vertex. In more details, a _label_ at each vertex contains the length of a shortest path towards each hub and, to retrieve the distance between two vertices, it suffices to find a common hub in their labels minimizing the sum of the two distances. The difficult point here is to find a small set of hubs _covering_ a shortest path for each pair of vertices in the graph, since in this way the resulting labeling is compact and, consequently the average query time is small.