  The problem of Approximate Nearest Neighbor (ANN) search is fundamental in
computer science and has benefited from significant progress in the past couple
of decades. However, most work has been devoted to pointsets whereas complex
shapes have not been sufficiently treated. Here, we focus on distance functions
between discretized curves in Euclidean space: they appear in a wide range of
applications, from road segments to time-series in general dimension. For
$\ell_p$-products of Euclidean metrics, for any $p$, we design simple and
efficient data structures for ANN, based on randomized projections, which are
of independent interest. They serve to solve proximity problems under a notion
of distance between discretized curves, which generalizes both discrete
Fr\'echet and Dynamic Time Warping distances. These are the most popular and
practical approaches to comparing such curves. We offer the first data
structures and query algorithms for ANN with arbitrarily good approximation
factor, at the expense of increasing space usage and preprocessing time over
existing methods. Query time complexity is comparable or significantly improved
by our algorithms, our algorithm is especially efficient when the length of the
curves is bounded.
