The nearest neighbor query ranks all objects in terms of their distance from a query object which can be one of the following types:
The neighboring objects are found in an incremental manner. In other words, having found the k nearest neighbors, in order to find the k+1st nearest neighbor, the algorithm does not recompute the set of k+1 nearest neighbors; it just finds the additional neighbor. The incremental nearest neighbor algorithm (see G. R. Hjaltason and H. Samet, Ranking in spatial databases in Advances in Spatial Databases - 4th Symposium, SSD'95, M. J. Egenhofer and J. R. Herring, Eds., Lecture Notes in Computer Science 951, Springer-Verlag, Berlin, 1995, 83-95; G. R. Hjaltason and H. Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems, 24(2):265-318, June 1999; and H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan-Kaufmann, San Francisco, pp. 490-501) makes use of a priority queue where the queue elements are the blocks of the underlying data structure as well as the objects themselves. The priority queue is ordered on the basis of the distance of its elements from the location of the query object which is a point in our implementation. In case of a tie between two spatial objects (i.e., two non-block objects have the same distance from query point p ) and if the distance is zero and if the object has extent and area (i.e., a rectangle), then use the distance from p to the nearest boundary of an object that contains p (if such an object exists) as the discriminator for the ordering.
The algorithm works in a top-down manner in the sense that as elements are removed from the queue, they are checked if they correspond to blocks that are not at the lowest level of the hierarchy (i.e., nonleaf nodes). If this is the case, then their immediate descendants (i.e., the sons) are inserted in the queue ordered according to their distance from the query object. Otherwise, the objects that they contain are inserted into the queue ordered according to their distance from the query object. If the element e that has been removed from the queue is a data object, then e is reported as the next nearest neighbor of the query object.
In order to be able to visualize the behavior of the incremental nearest neighbor algorithm, at any instance of time we distinguish between the following entities by using different colors in a consistent way for all of the data structures and data types: