面向多维对象的RC-反k近邻查询新方法

A new method of RkNN querry on multidimensional objects

分析现有反k近邻(reverse k nearest neighbor,RkNN)查询在效率、数据维度等方面的不足,提出基于R树结点覆盖值(R-tree’s cover-value)的RC-反k近邻查询方法.该方法需预先计算R树每个结点的覆盖值,采用过滤-精炼两步式处理方法,在过滤阶段采用两种剪枝启发式.该方法可有效处理数据库更新,适用于任意k值、任意维的对象集,查询结果精确,且计算量较小.实验结果表明,在k>6时RC-反k近邻查询时间比同类工作更短.

Reverse k-nearest neighbor（RkNN） queries have been popular in recent decades,although previous researches have some limitations,i.e.,the low query efficiency and inability in multidimensional case.The proposed RkNN method based on R-tree＇s cover-value,namely RC-RkNN,pre-calculated the cover-values of every node in the R-tree.This method was composed of filter stage and refinement stage.Two novel pruning heuristics were developed in the filter stage.Database can be updated efficiently with RC-RkNN,and querying results can be retrieved accurately.The value of k in RC-RkNN can be choosen arbitrarily and RC-RkNN is applicable to the multidimensional case.The simulation results on several real-world datasets and artificial datasets demonstrate that RC-RkNN need less querying time in comparison with other methods when k is larger than 6.