Title :
Efficient K-Nearest Neighbors query based on MR-tree
Author :
Hengfei, Zhang ; Zhiyuan, Zeng ; Xiaojun, Tan ; Jixiong, Chen
Author_Institution :
Digital Eng. & Simulation Res. Center, Huazhong Univ. of Sci. & Tech., Wuhan, China
Abstract :
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.
Keywords :
query processing; spatial data structures; tree data structures; tree searching; visual databases; K-nearest neighbors query; KNN query; branch-and-bound MR-tree traversal algorithm; maximal enclosed circle; minimum bound rectangle; multiapproximate R-tree; spatial dataset; spatial object; Computer science; Geographic Information Systems; Multidimensional systems; Nearest neighbor searches; Neural networks; Query processing; KNN query; Maximal Enclosed Circle; Multi-approximate R-tree; branch-and-bound;
Conference_Titel :
Advanced Computer Control (ICACC), 2010 2nd International Conference on
Conference_Location :
Shenyang
Print_ISBN :
978-1-4244-5845-5
DOI :
10.1109/ICACC.2010.5487094