Snapshot $k$ NN Queries

As described earlier, a snapshot $k$ NN query is to find the $k$ nearest neighbors from a static dataset. Snapshot queries are extensively studied by spatial database community [Hen94,RKV95,KSF$^+$96,PM97,KS97,SK98,HS99,CG99]. There have been many spatial indexes proposed for multidimensional points but the $R$ tree [Gut84] and its variants (especially R*-tree [BKSS90]) are the most popular ones. The most widely used approaches to answer $k$ NN queries [RKV95,HS99] use branch-and-bound algorithms on R-tree while maintaining a list of $k$ potential nearest neighbors in a priority queue.

Besides the branch-and-bound algorithms, there have also been attempts [KSF$^+$96] to use range queries to solve $k$ NN queries. Basic idea is to first find a region that guarantees to contain all $k$ NNs and then to use a range query to retrieve the potential $k$ NNs. The improvements to this algorithms were proposed in [CG99] by improving the region estimation. Seidl et al. [SK98] improved this algorithm by providing a better search technique of the $k$ NNs in the region.

As described earlier, most popular branch-and-bound algorithms [RKV95,HS99] traverse the R-tree to retrieve $k$ nearest neighbors. R-tree is traversed in depth-first manner in [RKV95] and in best-first search manner in [HS99]. Fig.  shows spatial objects and their corresponding R-tree. Below, we briefly describe these two popular R-tree traversal methods with the help of Fig. .