Bottom-up nearest neighbor search for R-trees

A new nearest neighbor (NN) search algorithm for R-trees was proposed that performed in a bottom-up manner. The proposed approach starts at the leaf level and traverses to the Root node. The experimental results demonstrate that the proposed NN search algorithm outperforms existing NN search algorithms which are based on the R-tree including the existing I/O optimal algorithm. The conventional R-trees were required to be modified to make the bottom-up approach possible. Two new pruning heuristics were also proposed where the first is the remnant property and the second is safe MBR property. The possible usage of the safe MBRs is to be investigated without the additional hash structure. It was found that the proposed approach outperforms existing approaches such as DFS and BFS without respect to the number of nearest neighbors.