Item

Abstract

We study the $c$-approximate near neighbor problem under the continuous
Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a
radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the
curves into a data structure that, given a query curve $q$ with $k$ vertices,
either returns an input curve with Fr\'echet distance at most $c\cdot \delta$
to $q$, or returns that there exists no input curve with Fr\'echet distance at
most $\delta$ to $q$. We focus on the case where the input and the queries are
one-dimensional polygonal curves -- also called time series -- and we give a
comprehensive analysis for this case. We obtain new upper bounds that provide
different tradeoffs between approximation factor, preprocessing time, and query
time.
Our data structures improve upon the state of the art in several ways. We
show that for any $0 < \varepsilon \leq 1$ an approximation factor of
$(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the
previously best result for $(2+\varepsilon)$. Moreover, we show that an
approximation factor of $(2+\varepsilon)$ can be obtained by using
preprocessing time and space $O(nm)$, which is linear in the input size, and
query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best
result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and
query time in $O(1)^k$. We complement our upper bounds with matching
conditional lower bounds based on the Orthogonal Vectors Hypothesis.
Interestingly, some of our lower bounds already hold for any super-constant
value of $k$. This is achieved by proving hardness of a one-sided sparse
version of the Orthogonal Vectors problem as an intermediate problem, which we
believe to be of independent interest.