  We propose $\kappa$-approximate nearest neighbor (ANN) data structures for
$n$ polygonal curves under the Fr\'{e}chet distance in $\mathbb{R}^d$, where
$\kappa \in \{1+\varepsilon,3+\varepsilon\}$ and $d \geq 2$. We assume that
every input curve has at most $m$ vertices, every query curve has at most $k$
vertices, $k \ll m$, and $k$ is given for preprocessing. The query times are
$\tilde{O}(k(mn)^{0.5+\varepsilon}/\varepsilon^d+ k(d/\varepsilon)^{O(dk)})$
for $(1+\varepsilon)$-ANN and
$\tilde{O}(k(mn)^{0.5+\varepsilon}/\varepsilon^d)$ for $(3+\varepsilon)$-ANN.
The space and expected preprocessing time are
$\tilde{O}(k(mnd^d/\varepsilon^d)^{O(k+1/\varepsilon^2)})$ in both cases. In
two and three dimensions, we improve the query times to
$O(1/\varepsilon)^{O(k)} \cdot \tilde{O}(k)$ for $(1+\varepsilon)$-ANN and
$\tilde{O}(k)$ for $(3+\varepsilon)$-ANN. The space and expected preprocessing
time improve to $O(mn/\varepsilon)^{O(k)} \cdot \tilde{O}(k)$ in both cases.
For ease of presentation, we treat factors in our bounds that depend purely on
$d$ as~$O(1)$. The hidden polylog factors in the big-$\tilde{O}$ notation have
powers dependent on $d$.
