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.
Die klassische Losung zur Berechnung kurzester Wege ist die Anwendung des Dijkstra Algorithmus, der in O(m + n log m) Zeit selbigen findet, wobei m die Anzahl Kanten ist und n die Anzahl der Knoten. Fur die Berechnung zwischen zwei beliebigen Knoten im US-Strasennetzwerk, bestehend aus ca. 24 Mio. Knoten und ca. 58 Mio. Kanten, dauert dies auf heutigen Rechnern mehr als eine Sekunde. Fur viele Anwendungen ist dies zu langsam. Obwohl es noch eine offene Frage ist, ob Dijkstra [1] fur solche Anfragen optimal ist, gibt es eine offensichtliche untere Schranke von Ω(m + n). Um schnellere, sublineare, Anfragezeiten zu erreichen, mus eine Vorverarbeitung stattfinden. Holger [2] stellten das Transitknoten-Konzept – ein allgemeines Konzept zur Auswahl einer Menge an Strasenknoten fur eine Vorberechnung – vor, auf welches im Folgenden naher eingegangen wird. We present a novel approach to graph partitioning based on the notion of . Our algorithm, called PUNCH, has two phases. The first phase performs a series of minimum-cut computations to identify and contract dense regions of the graph. This reduces the graph size, but preserves its general structure. The second phase uses a combination of greedy and local search heuristics to assemble the final partition. The algorithm performs especially well on road networks, which have an abundance of natural cuts (such as bridges, mountain passes, and ferries). In a few minutes, it obtains the best known partitions for continental-sized networks, significantly improving on previous results.  Highway hierarchies exploit hierarchical properties inherent in real-world road networks to allow fast and exact point-to-point shortest-path queries. A fast preprocessing routine iteratively performs two steps: First, it removes edges that only appear on shortest paths close to source or target; second, it identifies low-degree nodes and bypasses them by introducing shortcut edges. The resulting hierarchy of highway networks is then used in a Dijkstra-like bidirectional query algorithm to considerably reduce the search space size without losing exactness. The crucial fact is that ‘far away’ from source and target it is sufficient to consider only high-level edges. Experiments with road networks for a continent show that using a preprocessing time of around 15 min, one can achieve a query time of around 1ms on a 2.0GHz AMD Opteron. Highway hierarchies can be combined with goal-directed search, they can be extended to answer many-to-many queries, and they can be used as a basis for other speed-up techniques (e.g., for transit-node routing and highway-node routing).