All-Nearest-Neighbor Queries Processing in Spatial Databases

All-nearest-neighbor(All-NN) query processing for R-tree-like hierarchical access methods in spatial database system follows a batch paradigm, based on indexed nested-loop for NN querying of all objects and the single-directional expansion strategy in tree traversal. The authors propose a method for All-NN queries by exploiting location proximity of objects, when the primary data set P and the reference data set R are referred to the same one (P=R). A heuristic distance metric is used to reduce the volume of search space, instead of conventional MINDIST and MINMAXDIST metrics. And hence, the number of retrieved index nodes is reduced considerably, as well as the CPU time. The All-NN processing consists of two steps. NN query is performed within each leaf node by using plane-sweeping algorithm, in which all objects, as well as their nearest neighbor candidates, reside in current leaf node and, then an enhanced range query is performed to identify nearest neighbor and discard false alarms by retrieving objects that locate in other leaf nodes, based on the distance between objects and its might-be nearest neighbor of the first step. Experimental study shows the superb of this method over other approaches(e.g., PaS, BNN), in terms of IO cost and CPU time, by avoiding indexed nested-loop traversal, MINDIST and MINMAXDIST computation, and the maintenance of priority heap overhead.