【摘要】 提出了一种不同于R-tree和M-tree索引的RkNN搜索算法RiDistance,主要思想是将数据集索引到一棵B+树上来修剪搜索空间.首先,针对每个维度将所有对象进行排序;然后,基于排序信息将数据集分成一些小的分区并计算它们的单维索引距离;最后,使用一个filter-refine框架来处理RkNN查询.实验结果显示RiDistance是高效率的,它能修剪掉大部分的搜索空间,而且比序列扫描方法快几个数量级.更多还原

【Abstract】 Reverse k-nearest neighbor(RkNN) search is very useful in identifying the influence or the importance of objects.Existing methods for processing such search generally make use of traditional vector space index or metric space index,for example,R-tree or M-tree,to finish the task.However,we proposed an efficient RkNN algorithm,called RiDistance,which is different from conventional algorithms to process RkNN query,whose main idea is indexing the whole data set into a simple B+-tree to prune the search space such that the algorithm can early throw away the current compared object.Firstly,all objects are ordered at each dimension.Then,these objects are partitioned into many sub-partitions based on the ordered information,according to the partition principle of nearest neighbor,and the single dimensional distances are computed.At last,using a filter-refine search framework answers the RkNN query.The results of several experiments showed that RiDistance is effective and efficient because it can prune most search space and obtains several orders of magnitude performance improvement relative to sequential scan method in answering RkNN queries.更多还原