On the Approximate Nearest Neighbor Queries among Curves under the Fréchet Distance

preprint2021arXivOpen access

Abstract

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 Rd\Reals^d. Given a set of nn curves of size at most mm each in Rd\Reals^d, and a real fixed δ>0δ>0, we aim to preprocess into a data structure so that for any given query curve QQ of size kk, we can efficiently report all curves in whose Fréchet distances to QQ are at most δδ. In the case that kk 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)O(kd) query time, where $\D$ is the diameter of . Considering kk as part of the query slightly changes the space to $n \cdot O\big(\frac{1}{\eps}\big)^{md} $ with O(kd)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θ>0, and nn time-stamped points spread over mm regions in a map, for any query window WW, 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 WW in O(1)O(1) query time.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.