Distance oracle
In computing, a distance oracle (DO) is a data structure for calculating distances between vertices in a graph. Introduction. Let "G"("V","E") be an undirected, weighted graph, with "n" = |"V"| nodes and "m" = |"E"| edges. We would like to answer queries of the form "what is the distance between the nodes "s" and "t"?". One way to do this is just run the Dijkstra algorithm. This takes time formula_1, and requires no extra space (besides the graph itself). In order to answer many queries more efficiently, we can spend some time in pre-processing the graph and  creating an auxiliary data structure. A simple data structure that achieves this goal is a "matrix" which specifies, for each pair of nodes, the distance between them. This structure allows us to answer queries in constant time formula_2, but requires formula_3 extra space. It can be initialized in time formula_4 using an all-pairs shortest paths algorithm, such as the Floyd–Warshall algorithm. A DO lies between these two extremes. It uses less than formula_3 space in order to answer queries in less than formula_1 time. Most DOs have to compromise on accuracy, i.e. they don't return the accurate  distance but rather a constant-factor approximation of it. Approximate DO. Thorup and Zwick describe more than 10 different DOs. They then suggest a new DO that, for every "k", requires space formula_7, such that any subsequent distance query can be approximately answered in time formula_8. The approximate distance returned is of stretch at most formula_9, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and formula_9. The initialization time is formula_11. Some special cases include: Higher values of k do not improve the space or preprocessing time. DO for general metric  spaces. The oracle is built of a decreasing collection of "k"+1 sets of vertices: For every node "v", calculate its distance from each of these sets: For every node "v", calculate: For every "v", compute its "bunch": It is possible to show that the expected size of formula_43 is at most formula_44. For every bunch formula_43, construct a hash table that holds, for every formula_46, the distance formula_47. The total size of the data structure is formula_48 Having this structure initialized, the following algorithm finds the distance between two nodes, "u" and "v": It is possible to show that, in  each iteration, the distance formula_55 grows by at most formula_56. Since formula_57, there are at most "k"-1 iterations, so finally formula_58. Now by the triangle inequality, formula_59, so the distance returned is at most formula_60. Improvements. The above result was later improved by Patrascu and Roditty who suggest a DO of size formula_61 which returns a factor 2 approximation. Reduction from set intersection oracle. If there is a DO with an approximation factor of at most 2, then it is possible to build a set intersection oracle (SIO) with query time formula_2 and space requirements formula_63, where "n" is the  number of sets and "N" the sum of their sizes; see set intersection oracle#Reduction to approximate distance oracle. It is believed that the SIO problem does not have a non-trivial solution. I.e., it requires formula_64 space to answer queries in time formula_2, e.g. using an "n"-by-"n" table with the intersection between each two sets. If this conjecture is true, this implies that there is no DO with an approximation factor of less than 2 and a constant query time.