Speaker
Description
Siu-Wing Cheng and Haoqiang Huang
Abstract: We propose $\kappa$-approximate nearest neighbor (ANN) data structures for $n$ polygonal curves with at most $m$ vertices each under the Fr\'{e}chet distance in $\mathbb{R}^d$, where $\kappa \in \{1+\epsilon,3+\epsilon\}$ and $d \geq 2$. We assume that every query curve has at most $k$ vertices, $k \ll m$, and $k$ is given for preprocessing. The query times are $\tilde{O}(k(mn)^{0.5+\epsilon}/\epsilon^{O(d)} + k(d/\epsilon)^{O(dk)})$ for $(1+\epsilon)$-ANN and $\tilde{O}(k(mn)^{0.5+\epsilon}/\epsilon^{O(d)})$ for $(3+\epsilon)$-ANN. The space and expected preprocessing time are $\tilde{O}(k(mnd^d/\epsilon^d)^{O(k+1/\epsilon^2)})$ in both cases. In two and three dimensions, we improve the query times to $\tilde{O}(k/\epsilon^{O(k)})$ for $(1+\epsilon)$-ANN and $\tilde{O}(k)$ for $(3+\epsilon)$-ANN. The space and expected preprocessing time improve to $\tilde{O}(k(mn/\epsilon)^{O(k)})$ in both cases. For ease of presentation, we suppress factors in our bounds that depend purely on $d$. The hidden polylog factors in the big-$\tilde{O}$ notation have powers dependent on $d$.