On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911757096714240 |
|---|---|
| author | Gudmundsson, Joachim Pfeifer, John Seybold, Martin P. |
| author_facet | Gudmundsson, Joachim Pfeifer, John Seybold, Martin P. |
| contents | We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fréchet distance. Given an $n$ vertex trajectory $P$ and an $m$ vertex query trajectory $Q$, we seek to report a vertex-aligned sub-trajectory $P'$ of $P$ that is closest to $Q$, i.e. $P'$ must start and end on contiguous vertices of $P$. Since in real data $P$ typically contains a very large number of vertices, we focus on answering queries, without restrictions on $P$ or $Q$, using only precomputed structures of ${\mathcal{O}}(n)$ size.
We use three baseline algorithms from straightforward extensions of known work, however they have impractical performance on realistic inputs. Therefore, we propose a new Hierarchical Simplification Tree data structure and an adaptive clustering based query algorithm that efficiently explores relevant parts of $P$. The core of our query methods is a novel greedy-backtracking algorithm that solves the Fréchet decision problem using ${\cal O}(n+m)$ space and ${\cal O}(nm)$ time in the worst case.
Experiments on real and synthetic data show that our heuristic effectively prunes the search space and greatly reduces computations compared to baseline approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_10364 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance Gudmundsson, Joachim Pfeifer, John Seybold, Martin P. Computational Geometry Data Structures and Algorithms We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fréchet distance. Given an $n$ vertex trajectory $P$ and an $m$ vertex query trajectory $Q$, we seek to report a vertex-aligned sub-trajectory $P'$ of $P$ that is closest to $Q$, i.e. $P'$ must start and end on contiguous vertices of $P$. Since in real data $P$ typically contains a very large number of vertices, we focus on answering queries, without restrictions on $P$ or $Q$, using only precomputed structures of ${\mathcal{O}}(n)$ size. We use three baseline algorithms from straightforward extensions of known work, however they have impractical performance on realistic inputs. Therefore, we propose a new Hierarchical Simplification Tree data structure and an adaptive clustering based query algorithm that efficiently explores relevant parts of $P$. The core of our query methods is a novel greedy-backtracking algorithm that solves the Fréchet decision problem using ${\cal O}(n+m)$ space and ${\cal O}(nm)$ time in the worst case. Experiments on real and synthetic data show that our heuristic effectively prunes the search space and greatly reduces computations compared to baseline approaches. |
| title | On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2203.10364 |