  An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch
$\sigma \geq 1$ is a data structure that preprocesses an input graph $G$. When
queried with the triple $(s,t,F)$, where $s, t \in V$ and $F \subseteq E$
contains at most $f$ edges of $G$, the oracle returns an estimate
$\widehat{d}_{G-F}(s,t)$ of the distance $d_{G-F}(s,t)$ between $s$ and $t$ in
the graph $G-F$ such that $d_{G-F}(s,t) \leq \widehat{d}_{G-F}(s,t) \leq \sigma
d_{G-F}(s,t)$. For any positive integer $k \ge 2$ and any $0 < \alpha < 1$, we
present an $f$-DSO with sensitivity $f = o(\log n/\log\log n)$, stretch $2k-1$,
space $O(n^{1+\frac{1}{k}+\alpha+o(1)})$, and an
$\widetilde{O}(n^{1+\frac{1}{k} - \frac{\alpha}{k(f+1)}})$ query time.
  Prior to our work, there were only three known $f$-DSOs with subquadratic
space. The first one by Chechik et al. [Algorithmica 2012] has a stretch of
$(8k-2)(f+1)$, depending on $f$. Another approach is storing an $f$-edge
fault-tolerant $(2k-1)$-spanner of $G$. The bottleneck is the large query time
due to the size of any such spanner, which is $\Omega(n^{1+1/k})$ under the
Erd\H{o}s girth conjecture. Bil\`o et al. [STOC 2023] gave a solution with
stretch $3+\varepsilon$, query time $O(n^{\alpha})$ but space
$O(n^{2-\frac{\alpha}{f+1}})$, approaching the quadratic barrier for large
sensitivity. In the realm of subquadratic space, our $f$-DSOs are the first
ones that guarantee, at the same time, large sensitivity, low stretch, and
non-trivial query time. To obtain our results, we use the approximate distance
oracles of Thorup and Zwick [JACM 2005], and the derandomization of the $f$-DSO
of Weimann and Yuster [TALG 2013], that was recently given by Karthik and
Parter [SODA 2021].
