【作者】 陈健； 印鉴； 陈玲；

【Author】 CHEN Jian,YIN Jian,and CHEN Ling (Department of Computer Science,Sun Yat-sen University,Guangzhou 510275)

【机构】 中山大学计算机科学系；

【摘要】 k-最近邻居及其检索算法是计算机科学的主要核心问题之一,尤其在多维数据库系统的检索和查询方面起着相当重要的作用.近年来,k-最近邻居的逆问题逐渐得到人们广泛的关注.所谓逆k-最近邻居,就是在给定的数据集S中将查询点q视为其k-最近邻居的所有点的集合.深入研究了逆k-最近邻居的理论基础,并吸取了索引树对多维数据集整体特征良好的表达能力,提出了基于多维向量的动态索引结构RkNNTree及其检索方式RkNNQuery算法.实验结果表明,在多维数据集中,该算法比朴素的RkNN查询算法效率有显著的提高.更多还原

【Abstract】 k nearest neighbor problem is one of important topics in computer science,especially in points query and search in multi-dimensional database system.Recently,more and more attentions have been paid to its reverse version,which is known as"influence sets"problem.The reverse k nearest neighbor problem is to find all points in a data set that take a given query point as their k nearest neighbor.The related basic definitions and theories are given in this paper.Based on the good capability to represent feature of the whole data set of indexing structure,a new heuristic dynamic indexing tree structure RkNNTree and its related points query algorithm RkNNQuery are presented.The experimental results demonstrate that this algorithm can break the limitations of the past algorithms and enhance the performance efficiently.更多还原