Reverse NN Search Based on MR-Tree for Polygon Dataset

Many methods for answering RNN query have been proposed, which is a problem formulated only recently. But these approaches for processing such queries have at least one of the following deficiencies: (i) the query object and data object all are points and (ii) it is very limited to further improve search efficiency, which is indexed by conventional exterior approximate index method, such as R-tree, Grid-index and so on. Therefore, we develop algorithms of RNN query processing polygon data objects indexed by MR-tree to improve the search efficiency, which is indexed by multi-approximate index method. Firstly, the MR-tree index structure and method are introduced, and the RNN query for polygon data set is defined. Secondly, the algorithm of RNN based on MR-tree is presented. Thirdly, a series of tests of the RNN algorithm based on MR-tree indicate that the algorithm is applied and outperforms that based on the conventional index. So the proposed approach can be used to answer the RNN query for polygon data set and also is useful for current spatial database system.