论文标题
在实际的子区域范围内，在Fréchet距离下
On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
论文作者
论文摘要
我们研究了连续的Fréchet距离下在多边形曲线上最近邻邻查询的问题。考虑到$ n $顶点轨迹$ p $和$ m $顶点查询轨迹$ q $，我们试图报告一个与$ q $接近$ q $的顶点一致的子trajectory $ p'$ p'$ p $，即$ p'$必须在$ p $ $ p $的附加点上启动和结束。由于在实际数据$ p $中通常包含大量顶点，因此我们专注于回答查询，而无需限制$ p $或$ q $，仅使用$ {\ Mathcal {o}}}}（n）$ size的预先计算的结构。 我们使用已知工作的直接扩展中的三种基线算法，但是它们在现实输入上具有不切实际的性能。因此，我们提出了一个新的分层简化树数据结构和基于自适应聚类的查询算法，该算法有效地探索了$ p $的相关部分。我们查询方法的核心是一种新颖的贪婪折磨算法，该算法使用$ {\ cal o}（n+m）$ space和$ {\ cal o}（nm）$时间在最坏情况下解决Fréchet决策问题。 关于真实和合成数据的实验表明，与基线方法相比，我们的启发式启发式可有效地预留搜索空间，并大大降低了计算。
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.
