Nearest neighbor queries
- 22 May 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 24 (2) , 71-79
- https://doi.org/10.1145/568271.223794
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.Keywords
This publication has 6 references indexed in Scilit:
- Efficient processing of spatial joins using R-treesPublished by Association for Computing Machinery (ACM) ,1993
- The R*-tree: an efficient and robust access method for points and rectanglesPublished by Association for Computing Machinery (ACM) ,1990
- Linear clustering of objects with multiple attributesPublished by Association for Computing Machinery (ACM) ,1990
- Direct spatial search on pictorial databases using packed R-treesPublished by Association for Computing Machinery (ACM) ,1985
- R-treesPublished by Association for Computing Machinery (ACM) ,1984
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977