| Spatial query and optimization are emphases and difficulties of the related technologies in spatial database. The technology of reverse nearest neighbor query has become a hot subject of spatial query. Now, the technology of reverse nearest neighbor query is still at the initial stage, and the technical aspects are not mature, which still has some shortcomings. In this paper, the technologies of reverse nearest neighbor query are analyzed synthetically, and some new methods are proposed based on these, the material contents are as follows. Firstly, the technology of reverse nearest neighbor query is studied. The Cutting algorithm for space pruning is presented. Furthermore, the reverse nearest neighbor query is divided into the filtering stage and the validating stage and the algorithm for each stage is presented. In addition, the correctness of the algorithm is analyzed and proved through examples.Secondly, the technology of reverse k nearest neighbor query is studied. The k-Cutting algorithm for space pruning is presented. Furthermore, the algorithm for reverse nearest neighbor query is extended to reverse k nearest neighbor query. The algorithm for reverse k nearest neighbor query is also presented.Thirdly, the technology of reverse nearest neighbor query in ad-hoc subspaces is studied. The storge mode for reverse nearest neighbor query in ad-hoc subspaces is presented. Based on this mode, the algorithm which is divided into the the filtering stage and the validating stage is presented.The algorithm works without relying on multidimensional indexes.Finally, the algorithms in this paper are validated. The algorithm presented for reverse nearest neighbor query performs well and returns the exact results. The algorthim of reverse k nearest neighbor query has a good efficiency insolving the query when k is a bigger number. The algorithm of reverse nearest neighbor query in ad-hoc subspaces has a good performance in solving the query for multidimensional data. |
PDF Full Text Request