There are many types of queries in spatial database systems which are used by various applications such as CAD, VLSI design and GIS. A query type that is frequently encountered in spatial database systems is to find the nearest neighbor object to a given location. While there has been some research on the nearest neighbor query processing, the research was mostly concerned with the point data. That is, the query object of the nearest neighbor query is a point but not a non-point object such as a line segment, a polygon or a complex object.
In this paper we present an efficient method which can find the nearest neighbor object to a given nonzero-sized object using a R-tree variant indexing method. We propose a branch-and-bound R-tree traversal algorithm which prunes off unneeded nodes and searches the nearest neighbor object. In order to prune unneeded nodes efficiently we introduce the concepts of MINDIST and MINMAXDIST which are the distances between MBRs. The nearest neighbor query algorithm is implemented on the SHORE storage manager which has the R*-tree spatial access method. The SHORE storage manager was extended by developing modules necessary for the algorithm.
