Approximate nearest neighbor search (ANNS) is a long-studied problem in computational geometry  that has received considerable attentions by researchers in the community. In this paper, we revisit the problem in the presence of curves under the  Fr\'echet distance \Reals . Given a set %DIFDELCMD < {\cal %%% P of n curves of size at most m each in \mathbb{R \Reals and a real  \delta>0, we aim to preprocess %DIFDELCMD < {\cal %%% P into a data structure so that for any given query curve Q of size k,  report all curves in %DIFDELCMD < {\cal %%% P whose Fr\'echet distances to Q are at most \delta. In  case that k is known in the preprocessing stage \eps we propose a fully deterministic data structure whose space is O(n ( 32d\big(\big\{\big(}{\eps}}\big) ^{ 1/2 } /\varepsilon^3 )\big(}{\eps^2}}\big) ^{ d(k+1) } ) and can answer the \big\}\big)  \textsc{(1+ \varepsilon \eps )\delta-ANNS} queries in O(kd) query time \D  . Considering k as part of the query slightly changes the space to O( n ( 64d^{1/2/\varepsilon^3}%DIFDELCMD < }%%% )^{md\big({\eps}}\big) with O(kd) query time within  5 (1 + \varepsilon) approximation factor . We also \eps show that our data structure could give an alternative treatment of the approximate subtrajectory range counting (\textsc{ASRC ) problem studied by de Berg et al. ~\mbox{%DIFAUXCMD \cite{bcg-ffq-13}\hspace{0pt}%DIFAUXCMD } [ [ \eps\eps .
Approximate near-neighbors search (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\'echet distance in\Reals^d . Given a set %DIFDELCMD < {\cal %%% \P of n curves of size at most m each in \Reals^d, and a real fixed \delta>0, we aim to preprocess %DIFDELCMD < {\cal %%% \P into a data structure so that for any given query curve Q of size k, we can efficiently report all curves in %DIFDELCMD < {\cal %%% \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 \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 )\delta-ANNS} queries in O(kd) query time , where\D is the diameter of \P . Considering k as part of the query slightly changes the space to /\varepsilon^3}%DIFDELCMD < }%%% 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 \textsc{ searching problem studied by de Berg et al. }\hspace{0pt}%DIFAUXCMD } [8 . We also revisit 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, 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 \theta points whose times are within W in O(1) query time .
R
nearest neighbor
near-neighbors
A
. \%
R
attentions
attention
R
in the presence of
and propose the first data structure for
A
(continuous)
A
in
A
^d
R
P
\P
D
\mathbb{R
A
^d,
A
fixed
R
P
\P
A
we can efficiently
R
P
\P
A
the
R
known
given
A
, for any
A
>0
D
fully
D
O(n (
R
32d
n \cdot O
A
\max
A
\frac{\sqrt{d
R
1/2
kd
D
/\varepsilon^3
R
)
,
A
\frac{\D\sqrt{d
R
d(k+1)
kd
D
) and can answer the
A
that can answer
D
\varepsilon
A
, where
A
is the diameter of \P
D
O( n (
D
64d^{1/2
R
)^{md
n \cdot O
A
\frac{1
A
^{md
A
an approximation factor of
D
(1
D
\varepsilon) approximation factor . We also
A
. We
R
data structure could
generic data structure for ANNS can
D
counting (
D
ASRC
R
)
searching
D
~\mbox{%DIFAUXCMD \cite{bcg-ffq-13
A
8
A
. We also revisit the time-window data structure for spatial density maps in
A
6
A
. Given \theta>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/
A
^2) and construction time O((n+m)/
A
^2) that can approximately return the regions containing at least \theta points whose times are within W in O(1) query time