  For an undirected unweighted graph $G=(V,E)$ with $n$ vertices and $m$ edges,
let $d(u,v)$ denote the distance from $u\in V$ to $v\in V$ in $G$. An
$(\alpha,\beta)$-stretch approximate distance oracle (ADO) for $G$ is a data
structure that given $u,v\in V$ returns in constant (or near constant) time a
value $\hat d (u,v)$ such that $d(u,v) \le \hat d (u,v) \le \alpha\cdot d(u,v)
+ \beta$, for some reals $\alpha >1, \beta$. If $\beta = 0$, we say that the
ADO has stretch $\alpha$.
  Thorup and Zwick~\cite{thorup2005approximate} showed that one cannot beat
stretch 3 with subquadratic space (in terms of $n$) for general graphs.
P\v{a}tra\c{s}cu and Roditty~\cite{patrascu2010distance} showed that one can
obtain stretch 2 using $O(m^{1/3}n^{4/3})$ space, and so if $m$ is subquadratic
in $n$ then the space usage is also subquadratic. Moreover, P\v{a}tra\c{s}cu
and Roditty~\cite{patrascu2010distance} showed that one cannot beat stretch 2
with subquadratic space even for graphs where $m=\tilde{O}(n)$, based on the
set-intersection hypothesis.
  In this paper we explore the conditions for which an ADO can be stored using
subquadratic space while supporting a sub-2 stretch. In particular, we show
that if the maximum degree in $G$ is $\Delta_G \leq O(n^{1/2-\varepsilon})$ for
some $0<\varepsilon \leq 1/2$, then there exists an ADO for $G$ that uses
$\tilde{O}(n^{2-\frac {2\varepsilon}{3}})$ space and has a sub-2 stretch.
  Moreover, we prove a conditional lower bound, based on the set intersection
hypothesis, which states that for any positive integer $k \leq \log n$,
obtaining a sub-$\frac{k+2}{k}$ stretch for graphs with maximum degree
$\Theta(n^{1/k})$ requires quadratic space. Thus, for graphs with maximum
degree $\Theta(n^{1/2})$, obtaining a sub-2 stretch requires quadratic space.
