# Item

ITEM ACTIONSEXPORT

Released

Paper

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

##### 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.

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.