  The Fr\'{e}chet distance is one of the most studied distance measures between
curves $P$ and $Q$. The data structure variant of the problem is a longstanding
open problem: Efficiently preprocess $P$, so that for any $Q$ given at query
time, one can efficiently approximate their Fr\'{e}chet distance. There exist
conditional lower bounds that prohibit $(1 + \varepsilon)$-approximate
Fr\'{e}chet distance computations in subquadratic time, even when preprocessing
$P$ using any polynomial amount of time and space. As a consequence, the
problem has been studied under various restrictions: restricting $Q$ to be a
(horizontal) segment, or requiring $P$ and $Q$ to be so-called \emph{realistic}
input curves.
  We give a data structure for $(1+\varepsilon)$-approximate discrete
Fr\'{e}chet distance in any metric space $\mathcal{X}$ between a realistic
input curve $P$ and any query curve $Q$. After preprocessing the input curve
$P$ (of length $|P|=n$) in $O(n \log n)$ time, we may answer queries specifying
a query curve $Q$ and an $\varepsilon$, and output a value $d(P,Q)$ which is at
most a $(1+\varepsilon)$-factor away from the true Fr\'{e}chet distance between
$Q$ and $P$. Our query time is asymptotically linear in $|Q|=m$,
$\frac{1}{\varepsilon}$, $\log n$, and the realism parameter $c$ or $\kappa$.
Our data structure is the first to: adapt to the approximation parameter
$\varepsilon$ at query time, handle query curves with arbitrarily many
vertices, work for any ambient space of the curves, or be dynamic.
  The method presented in this paper simplifies and generalizes previous
contributions to the static problem variant. We obtain efficient queries (and
therefore static algorithms) for Fr\'{e}chet distance computation in
high-dimensional spaces and other ambient metric spaces.
