Faster Nearest Neighbors Queries on Geographic Data

In the context of geographic data, we argue that concatenating segments of inverted quadratic functions yields suitable bounds and formalize an optimization problem with respect to the number of segments. We then present an approximation algorithm that computes such functions efficiently. The basic idea is to exploit geometrical properties of the underlying problem, allowing us to find suitable segments using linear programming and to obtain guarantees on the quality of the approximation.

We complement our theoretical analysis with an empirical evaluation of our algorithm on real-world data. With respect to run times, we observe that the resulting technique improves upon conventional methods for answering kNN queries, especially for larger k. In particular, we obtain speed-up factors of up to 18. Additionally, the experiments indicate that our method requires little space.