Nearest neighbor queries

TLDR

In Geographic Information Systems, k‑nearest‑neighbor queries are common and require search algorithms distinct from those used for location or range queries. The paper proposes an efficient branch‑and‑bound R‑tree traversal algorithm for nearest‑neighbor queries, generalized to k‑nearest neighbors. The algorithm employs branch‑and‑bound traversal of R‑trees, using optimistic and pessimistic metrics to guide search ordering and pruning. Experiments demonstrate that the algorithm scales efficiently and that the metrics accurately guide pruning, yielding strong performance.

Abstract

A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range queries. In this paper we present an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. We also discuss metrics for an optimistic and a pessimistic search ordering strategy as well as for pruning. Finally, we present the results of several experiments obtained using the implementation of our algorithm and examine the behavior of the metrics and the scalability of the algorithm.