中文摘要：

摘要： 在空间数据索引与查询研究领域中，反向k最近邻（RNNk）问题作为反向最近邻问题的泛化扩展近来受到更多关注。所谓RNNk查询就是找到所有以给定查询点为k个最近邻之一的对象点。为了有效地进行RNNk查询，利用分级的Voronoi cell和空间区域划分方法对查询结果进行有效过滤，避免了过多次最近邻查找计算。在初步得到的RNNk结果中，有针对性地分别利用平行于分割线的扫描线和局部扩展的查询区域Q进一步限定了RNN候选点。近似最小平均距离（AMAD）计算则可由近似的RNNk查询结果得到且不受k取值限制。实验结果表明了在3种不同数据分布情况下，本文算法与近似方法的效率和有效性。因此，通过充分利用对数据的过滤与查询空间修剪的近似方法，得到了具有较高查全率和准确率的近似查询和计算。

英文摘要：

Reverse k nearest neighbor （RNNk） is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data points which use a query point as one of their k nearest neighbors. To answer the RNNk of queries efficiently, the properties of the Voronoi cell and the space-dividing regions are applied. The RNNk of the given point can be found without computing its nearest neighbors every time by using the rank Voronoi cell. With the elementary RNNk query result, the candidate data points of reverse nearest neighbors can he further limited by the approximation with sweepline and the partial extension of query region Q. The approximate minimum average distance （AMAD） can be calculated by the approximate RNNk without the restriction of k. Experimental results indicate the efficiency and the effectiveness of the algorithm and the approximate method in three varied data distribution spaces. The approximate query and the calculation method with the high precision and the accurate recall are obtained by filtrating data and pruning the search space.