论文标题
在Fréchet距离下的曲线之间的大约最近的邻居查询
On the Approximate Nearest Neighbor Queries among Curves under the Fréchet Distance
论文作者
论文摘要
在计算几何形状中，大约接近近脑搜索（\ textsc {anns}）是一个长期研究的问题。受到社区研究人员的关注的％。在本文中，我们重新审视了问题，并提出了（连续）fréchet距离下的曲线的第一个数据结构，以$ \ reals^d $。给定$ n $的$ n $曲线，最多最多$ m $ $ m $在$ \ reals^d $中，以及真正的固定$δ> 0 $，我们的目标是将$¶$预先添加到数据结构中，以便在任何给定的查询曲线$ q $ q $ q $ q $ a $ k $中，我们可以在$¶$ $ $ $ $ q $上有效地报告所有曲线。在预处理阶段给出$ k $的情况下，对于任何$ \ eps> 0 $，我们提出了一个确定的数据结构，其空间为$ n \ cdot o \ big（\ max \ max \ big \ big {\ big（\ frac {\ frac {\ sqrt {d}}}}} {\ eps} {\ eps} {\ eps} {\ big） \ big（\ frac {\ d \ sqrt {d}} {\ eps^2} \ big）考虑$ k $作为查询的一部分，将空间稍微更改为$ n \ cdot o \ big（\ frac {1} {\ eps} \ big）^{md）^{md} $，其中$ o（kd）$查询时间在$ 5+\ eps $的近似值内。我们表明，我们的ANN的通用数据结构可以对De Berg等人研究的近似亚横向范围搜索问题提供替代处理。 [8]。我们还重新访问[6]中空间密度图的时间窗口数据结构。给定的$θ> 0 $，以及$ n $的时间平台点分布在地图上的$ m $区域，对于任何查询窗口$ w $，我们提出了一个尺寸$ o（n/\ eps^2）$和构造时间$ o（（（n+m）/\ eps^2）$的数据结构，至少可以返回包含$ ch $ $ ch y yey $ query的$ o o o o o o o o o的$ o o o o o o o o o o o point $ o o o o o o o point $ o o o o。
Approximate near-neighbors search (\textsc{ANNS}) is a long-studied problem in computational geometry. %that has received considerable attention by researchers in the community. In this paper, we revisit the problem and propose the first data structure for curves under the (continuous) Fréchet distance in $\Reals^d$. Given a set $¶$ of $n$ curves of size at most $m$ each in $\Reals^d$, and a real fixed $δ>0$, we aim to preprocess $¶$ into a data structure so that for any given query curve $Q$ of size $k$, we can efficiently report all curves in $¶$ whose Fréchet distances to $Q$ are at most $δ$. In the case that $k$ is given in the preprocessing stage, for any $\eps>0$ we propose a deterministic data structure whose space is $n \cdot O\big(\max\big\{\big(\frac{\sqrt{d}}{\eps}\big)^{kd}, \big(\frac{\D\sqrt{d}}{\eps^2}\big)^{kd}\big\}\big)$ that can answer \textsc{$(1+\eps)δ$-ANNS} queries in $O(kd)$ query time, where $\D$ is the diameter of $¶$. Considering $k$ as part of the query slightly changes the space to $n \cdot O\big(\frac{1}{\eps}\big)^{md} $ with $O(kd)$ query time within an approximation factor of $5+\eps$. We show that our generic data structure for ANNS can give an alternative treatment of the approximate subtrajectory range searching problem studied by de Berg et al. [8]. We also revisit the time-window data structure for spatial density maps in [6]. Given $θ>0$, and $n$ time-stamped points spread over $m$ regions in a map, for any query window $W$, we propose a data structure of size $O(n/\eps^2)$ and construction time $O((n+m)/\eps^2)$ that can approximately return the regions containing at least $θ$ points whose times are within $W$ in $O(1)$ query time.
