English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons228472

Nusser,  André
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2107.07792.pdf
(Preprint), 889KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bringmann, K., Driemel, A., Nusser, A., & Psarros, I. (2021). Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance. Retrieved from https://arxiv.org/abs/2107.07792.


Cite as: https://hdl.handle.net/21.11116/0000-0009-B43F-6
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.