Approximate Distance Oracles with Faster Preprocessing and Query Time

Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k>=2, we show that for some constant c, a (2k-1)-approximate distance oracle for G of size O(kn^{1 + 1/k}) can be constructed in O(\min\{kmn^{1/k},\sqrt km + kn^{1 + c/\sqrt k}\}) time and can answer queries in O(\log k) time. This improves the O(k) query time of Thorup and Zwick and breaks the quadratic preprocessing time bound of Baswana and Kavitha for m = o(n^2) and all $k\geq 6$. When m = \Omega(n^{1 + c/\sqrt k}) and k = O(1), our oracle is optimal w.r.t.\ both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erd\H{o}s. We also give, for any \epsilon > 0, an oracle of size O(kn^{1 + 1/k}) which answers (2 + \epsilon)k-approximate distance queries in O(1/\epsilon) time. At the cost of a k-factor in size, this improves the 128k approximation achieved by the constant query time oracle of Mendel and Naor. We can match their O(n^{1 + 1/k}) size bound for any constant \epsilon > 0 and k = O(\log n/\log\log n).