A Dynamic Data Structure for k-Nearest Neighbors Queries

Abstract

We present an insertion-only data structure that supports k-nearest neighbors queries for a set of n point sites in O(Q(n)log n + k) time, based on any static data structure that can perform k 0 -nearest neighbors queries in O(Q(n) + k 0 ) time. The key component is a general query algorithm that allows us to find k-nearest neighbors spread over t substructures simultaneously, thus reducing the O(tk) term in the query time to O(k). Applying this to the logarithmic method yields an insertion-only data structure with both efficient insertion and query time. We apply our method in the plane for the Euclidean and geodesic distance. We then briefly discuss the main difficulties to achieve a similar running time in the fully dynamic case.