English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Approximate near-neighbors search (\textsc{ANNS}) is a long-studied problemin computational geometry. %that has received considerable attention byresearchers in the community. In this paper, we revisit the problem and proposethe first data structure for curves under the (continuous) Fr\'echet distancein $\Reals^d$. Given a set $\P$ of $n$ curves of size at most $m$ each in$\Reals^d$, and a real fixed $\delta>0$, we aim to preprocess $\P$ into a datastructure so that for any given query curve $Q$ of size $k$, we can efficientlyreport all curves in $\P$ whose Fr\'echet distances to $Q$ are at most$\delta$. 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 \cdotO\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)\delta$-ANNS} queries in $O(kd)$ query time, where $\D$ is thediameter of $\P$. Considering $k$ as part of the query slightly changes thespace to $n \cdot O\big(\frac{1}{\eps}\big)^{md} $ with $O(kd)$ query timewithin an approximation factor of $5+\eps$. We show that our generic datastructure for ANNS can give an alternative treatment of the approximatesubtrajectory range searching problem studied by de Berg et al. [8]. We alsorevisit the time-window data structure for spatial density maps in [6]. Given$\theta>0$, and $n$ time-stamped points spread over $m$ regions in a map, forany query window $W$, we propose a data structure of size $O(n/\eps^2)$ andconstruction time $O((n+m)/\eps^2)$ that can approximately return the regionscontaining at least $\theta$ points whose times are within $W$ in $O(1)$ querytime.

On the Approximate Nearest Neighbor Queries among Curves under the Fr\'echet Distance