Among the various types computations on graphs, the most fundamental is the distance query, which seeks the length of a shortest path between two vertices. The distance query is important because it is the basis of many other query types in fields such as transportation planning [1]}, network design [2]}, operational research [3]}, [4]}, [5]}, and graph databases [6]}. When the graph is large, direct computation of the distance becomes impractical, so there is a need for preprocessing methods that can efficiently approximate the distance while still being reasonably accurate.
