$(1+varepsilon)$-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension

We consider the $(1+varepsilon)$-Approximate Nearest Neighbour (ANN) Problem for polygonal curves in $d$-dimensional space under the Fréchet distance and ask to what extent known data structures for doubling spaces can be applied to this problem. Initially, this approach does not seem viable, since the doubling dimension of the target space is known to be unbounded — even for well-behaved polygonal curves of constant complexity in one dimension. In order to overcome this, we identify a subspace of curves which has bounded doubling dimension and small Gromov-Hausdorff distance to the target space. We then apply state-of-the-art techniques for doubling spaces and show how to obtain a data structure for the $(1+varepsilon)$-ANN problem for any set of parametrized polygonal curves. The expected preprocessing time needed to construct the data-structure is $F(d,k,S,varepsilon)nlog n$ and the space used is $F(d,k,S,varepsilon)n$, with a query time of $F(d,k,S,varepsilon)log n + F(d,k,S,varepsilon)^{-log(varepsilon)}$, where $F(d,k,S,varepsilon)=Oleft(2^{O(d)}kPhi(S)varepsilon^{-1}right)^k$ and $Phi(S)$ denotes the spread of the set of vertices and edges of the curves in $S$. We extend these results to the realistic class of $c$-packed curves and show improved bounds for small values of $c$.

  • Published in:
  • Type:
  • Authors:
    Conradi, Jacobus; Driemel, Anne; Kolbe, Benedikt
  • Year:

Citation information

Conradi, Jacobus; Driemel, Anne; Kolbe, Benedikt: $(1+varepsilon)$-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension, arXiv, 2023, https://arxiv.org/abs/2307.08521, Conradi.etal.2023a,

Associated Lamarr Researchers

lamarr institute person Driemel Anne e1664271117365 - Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)

Prof. Dr. Anne Driemel

Principal Investigator Hybrid ML to the profile