A Filter-and-Refinement-Algorithm for Range Queries Based on the Fréchet Distance (GIS Cup)

We present an algorithm for the following problem: Given a dataset D: = {T1,..., Tn} of data trajectories and a set Q: = {Q1,..., Qm} of query trajectories, each of which with a distance parameter ϵi ≥ 0, report, for each query trajectory Qi, all data trajectories within a Fréchet distance of at most ϵi. As computing the Fréchet distance is known to be computationally demanding, our algorithm uses a filter-and-refinement approach to reduce the number of query/data candidate pairs for which the Fréchet distance needs to be computed exactly. As usually, we first use a hash-based range searching data structure to filter out candidate pairs whose minimum bounding rectangles are too far away. We then make extensive use of geometric properties of the Fréchet distance to prune further candidate pairs in a series of further steps of the filter phase. In the refinement phase, i.e., when exactly computing the Fréchet distance, we keep track of the boundary of the reachable space in the free space diagram to speed up the computation. Our algorithm is capable of using multiple threads in parallel; this is used to overlay the filter and refinement steps as well as the reporting of the output.