  In 2001 Thorup and Zwick devised a distance oracle, which given an $n$-vertex
undirected graph and a parameter $k$, has size $O(k n^{1+1/k})$. Upon a query
$(u,v)$ their oracle constructs a $(2k-1)$-approximate path $\Pi$ between $u$
and $v$. The query time of the Thorup-Zwick's oracle is $O(k)$, and it was
subsequently improved to $O(1)$ by Chechik. A major drawback of the oracle of
Thorup and Zwick is that its space is $\Omega(n \cdot \log n)$. Mendel and Naor
devised an oracle with space $O(n^{1+1/k})$ and stretch $O(k)$, but their
oracle can only report distance estimates and not actual paths. In this paper
we devise a path-reporting distance oracle with size $O(n^{1+1/k})$, stretch
$O(k)$ and query time $O(n^\epsilon)$, for an arbitrarily small $\epsilon > 0$.
In particular, our oracle can provide logarithmic stretch using linear size.
Another variant of our oracle has size $O(n \log\log n)$, polylogarithmic
stretch, and query time $O(\log\log n)$.
  For unweighted graphs we devise a distance oracle with multiplicative stretch
$O(1)$, additive stretch $O(\beta(k))$, for a function $\beta(\cdot)$, space
$O(n^{1+1/k} \cdot \beta)$, and query time $O(n^\epsilon)$, for an arbitrarily
small constant $\epsilon >0$. The tradeoff between multiplicative stretch and
size in these oracles is far below girth conjecture threshold (which is stretch
$2k-1$ and size $O(n^{1+1/k})$). Breaking the girth conjecture tradeoff is
achieved by exhibiting a tradeoff of different nature between additive stretch
$\beta(k)$ and size $O(n^{1+1/k})$. A similar type of tradeoff was exhibited by
a construction of $(1+\epsilon,\beta)$-spanners due to Elkin and Peleg.
However, so far $(1+\epsilon,\beta)$-spanners had no counterpart in the
distance oracles' world.
  An important novel tool that we develop on the way to these results is a
{distance-preserving path-reporting oracle}.
