  In the $(1+\varepsilon,r)$-approximate near-neighbor problem for curves
(ANNC) under some distance measure $\delta$, the goal is to construct a data
structure for a given set $\mathcal{C}$ of curves that supports approximate
near-neighbor queries: Given a query curve $Q$, if there exists a curve
$C\in\mathcal{C}$ such that $\delta(Q,C)\le r$, then return a curve
$C'\in\mathcal{C}$ with $\delta(Q,C')\le(1+\varepsilon)r$. There exists an
efficient reduction from the $(1+\varepsilon)$-approximate nearest-neighbor
problem to ANNC, where in the former problem the answer to a query is a curve
$C\in\mathcal{C}$ with $\delta(Q,C)\le(1+\varepsilon)\cdot\delta(Q,C^*)$, where
$C^*$ is the curve of $\mathcal{C}$ closest to $Q$. Given a set $\mathcal{C}$
of $n$ curves, each consisting of $m$ points in $d$ dimensions, we construct a
data structure for ANNC that uses $n\cdot O(\frac{1}{\varepsilon})^{md}$
storage space and has $O(md)$ query time (for a query curve of length $m$),
where the similarity between two curves is their discrete Fr\'echet or dynamic
time warping distance. Our method is simple to implement, deterministic, and
results in an exponential improvement in both query time and storage space
compared to all previous bounds. Further, we also consider the asymmetric
version of ANNC, where the length of the query curves is $k \ll m$, and obtain
essentially the same storage and query bounds as above, except that $m$ is
replaced by $k$. Finally, we apply our method to a version of approximate range
counting for curves and achieve similar bounds.
