Efficient K-Nearest Neighbors query based on MR-tree

摘要

We present an approach based on novel structure called Multi-approximate R-tree (MR-tree) to performing the K-Nearest Neighbors (KNN) query efficiently and accurately in this paper. Maximal Enclosed Circle (MEC) is introduced to express an object approximately with Minimum Bound Rectangle (MBR). The introducing of the MEC improves the accuracy of the approximate expression of the spatial objects. We also discussed the implementation of the branch-and-bound MR-Tree traversal algorithm derived from R-Tree traversal algorithm. The metrics used in the traversal algorithm are the emphases in our discussion. Factors of the spatial dataset impact the performance of the KNN query and are considered separately in our designing of the experiments. We give some guide lines for the using of our approach with these factors. Finally, we presented the results of several experiments conducted using different structures to demonstrate the effectiveness and proved the efficiency enhancement of the MR-Tree over other structures.