  We study the problem of sub-trajectory nearest-neighbor queries on polygonal
curves under the continuous Fr\'echet distance. Given an $n$ vertex trajectory
$P$ and an $m$ vertex query trajectory $Q$, we seek to report a vertex-aligned
sub-trajectory $P'$ of $P$ that is closest to $Q$, i.e. $P'$ must start and end
on contiguous vertices of $P$. Since in real data $P$ typically contains a very
large number of vertices, we focus on answering queries, without restrictions
on $P$ or $Q$, using only precomputed structures of ${\mathcal{O}}(n)$ size.
  We use three baseline algorithms from straightforward extensions of known
work, however they have impractical performance on realistic inputs. Therefore,
we propose a new Hierarchical Simplification Tree data structure and an
adaptive clustering based query algorithm that efficiently explores relevant
parts of $P$. The core of our query methods is a novel greedy-backtracking
algorithm that solves the Fr\'echet decision problem using ${\cal O}(n+m)$
space and ${\cal O}(nm)$ time in the worst case.
  Experiments on real and synthetic data show that our heuristic effectively
prunes the search space and greatly reduces computations compared to baseline
approaches.
