Many graph processing algorithms require determination of shortest-path distances between arbitrary numbers of node pairs. Since computation of exact distances between all node-pairs of a large graph, e.g., 10M nodes and up, is prohibitively expensive both in computational time and storage space, distance approximation is often used in place of exact computation. A distance oracle is a data structure that answers inter-point distance queries more efficiently than in standard O(n 2 ) in time or storage space for an n node graph, e.g., in O(nlogn). In this paper, we present a novel and scalable distance oracle that leverages the hyperbolic core of real-world large graphs for fast and scalable distance approximation via spanning trees. We show empirically that the proposed oracle significantly outperforms prior oracles on a random set of test cases drawn from public domain graph libraries. There are two sets of prior work against which we benchmark our approach. The first set, which often outperforms all other oracles, employs embedding of the graph into low dimensional Euclidean spaces with carefully constructed hyperbolic distances, but provides no guarantees on the distance estimation error. The second set leverages Gromov-type tree contraction of the graph with the additive error guaranteed not to exceed 2δ logn, where δ is the hyperbolic constant of the graph. We show that our proposed oracle 1) is significantly faster than those oracles that use hyperbolic embedding (first set) with similar approximation error and, perhaps surprisingly, 2) exhibits substantially lower average estimation error compared to Gromovlike tree contractions (second set). We substantiate our claims through numerical computations on a collection of a dozen real world networks and synthetic test cases from multiple domains, ranging in size from 10s of thousand to 10s of millions of nodes.
Exact Distance Oracles. Since exact distance oracles require the computation or storage of all pair shortest path, we do not consider these (e.g., @cite_11 @cite_22 and the references therein) in our comparison. We observe that even with the best combination of engineering insights, all-pairs shortest path computation remains far too slow for large graphs with @math nodes or edges and beyond, and this is especially unmanageable when these graphs do not fit in the main memory of the computing device. Also, we do not consider the oracles that have @math query complexity (e.g., @cite_35 @cite_16 @cite_36 ), as these are unlikely to yield efficient solutions.
@cite_35 @cite_22 @cite_36 @cite_16 @cite_11
2206683514 2146583842 2012688658 2005945380
We present distance oracles for weighted undirected graphs that return distances of stretch less than 2. For the realistic case of sparse graphs, our distance oracles exhibit a smooth three-way trade-off between space, stretch and query time --- a phenomenon that does not occur in dense graphs. In particular, for any positive integer t and for any 1 ≤ α ≤ n, our distance oracle is of size O(m + n2 α) and returns distances of stretch at most (1 + 2 t+1) in time O((αμ)t), where μ = 2m n is the average degree of the graph. The query time can be further reduced to O((α + μ)t) at the expense of a small additive stretch. We study hierarchical hub labelings for computing shortest paths. Our new theoretical insights into the structure of hierarchical labels lead to faster preprocessing algorithms, making the labeling approach practical for a wider class of graphs. We also find smaller labels for road networks, improving the query speed. We present a distance oracle that, for weighted graphs with n vertices and m edges, is of size 8n4 3m1 3log2 3n and returns stretch-2 distances in constant time. Our oracle achieves bounds identical to the constant-time stretch-2 oracle of Pǎtrascu and Roditty, but admits significantly simpler construction and proofs. We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search from every vertex. Seemingly too obvious and too inefficient at first glance, the key ingredient introduced here is pruning during breadth-first searches. While we can still answer the correct distance for any pair of vertices from the labels, it surprisingly reduces the search space and sizes of labels. Moreover, we show that we can perform 32 or 64 breadth-first searches simultaneously exploiting bitwise operations. We experimentally demonstrate that the combination of these two techniques is efficient and robust on various kinds of large-scale real-world networks. In particular, our method can handle social networks and web graphs with hundreds of millions of edges, which are two orders of magnitude larger than the limits of previous exact methods, with comparable query time to those of previous methods.