一种度量空间中的可逆近邻搜索算法  

A reverse nearest neighbor search algorithm in metric space

作　　者：蒋涛[1] 冯玉才[1] 李国徽[1] 朱虹[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2009年第8期23-26,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家高技术研究发展计划资助项目(2007AA01Z309;2006AA01Z430);国土资源部三峡库区三期地质灾害防治重大科研专项基金资助项目(SXKY3-6-3)

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

关 键 词：数据挖掘 算法 索引 度量空间 可逆近邻 分区 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]