GRkNN:空间数据库中组反k最近邻查询

摘要：

反k最近邻(Reverse k-Nearest-Neighbor,RkNN)查询是在k最近邻(k-Nearest-Neighbor,kNN)查询问题的基础上产生的,获得将查询对象作为kNN的数据对象集合,RkNN可以用于评价查询对象的影响力.根据实际应用中需要查询一组对象的RkNN,如评价连锁店或商业区的影响.文中提出了针对空间数据库的组反k最近邻(Group RkNN,GRkNN)的概念,并设计了相关算法.查询点集合是一组邻近的空间对象,计算查询对象的最小覆盖圆,将最小覆盖圆中的对象作为一个整体进行过滤,设计了基于R树的剪枝方法,通过提炼获取了最终的GRkNN结果.针对真实数据集进行的大量实验表明,提出的GRkNN算法的效率明显优于目前最好的RkNN算法.

关键词：反最近邻、GRkNN查询、R树、最小覆盖圆

所属期刊栏目：33

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61070024;国家"十一五"科技支撑计划2008BAJ08B08-04,2006BAJ11B07-01;辽宁省自然科学基金20071004

在线出版日期：2011-03-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：2229-2238