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

• 作者: 于程程 孙焕良 宋晓宇 许景科
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 反最近邻 GRkNN查询 R树 最小覆盖圆
• 年，卷（期）: 2010,（12）
• 页码范围: 2229-2238
• 分类号: TP311
• 字数: 7651字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.02229

摘要

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