Nearest neighbor search using r-trees

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 special search algorithms. This paper introduces 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.