On approximate near-neighbors search under the (continuous) Frechet distance in higher dimensions

Previous studies on Approximate Near-Neighbors Search (ANNS) among curves are either focused on curves in R-1 or under the discrete Frechet distance. In this paper, we propose the first data structure for curves under the (continuous) Frechet distance in higher dimensions. Given a set P of n curves each with number of vertices at most m in R-d, and a fixed delta > 0, we aim to preprocess P into a data structure so that for any given query curve Q with k vertices, we can efficiently report all curves in P whose Frechet distances to Q are at most delta. In the case that k is given in the preprocessing stage, for any epsilon > 0 we propose a deterministic data structure whose space is n center dot O (max{(root d/epsilon)(kd), (D root d/epsilon(2))(kd)}) that can answer (1 + epsilon)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 n center dot O (1/epsilon)(md) with O (kd) query time within an approximation factor of 5 + epsilon. Moreover, 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. [1]. (c) 2023 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes the first data structure for curves under the (continuous) Frechet distance in higher dimensions, which can efficiently report all curves with distances less than a given value to a query curve. For a given k value in the preprocessing stage, we propose a deterministic data structure that can answer (1 + epsilon)delta-ANNS queries in O (kd) query time, where D is the diameter of P.