一种障碍空间中的反k最近邻查询方法

• 作者: 于戈 于晓楠 张天成 谷峪
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 空间查询 反k最近邻(RkNN) 障碍空间 Voronoi图
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 数据库年会优秀论文
• 页码范围: 1917-1925
• 分类号: TP311
• 字数: 6532字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2011.01917

摘要

随着基于位置的服务(LBS)和物联网的快速发展,空间查询技术越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用.近几年,已有较多对于查询前k个反最近邻对象(RkNN)的研究,其中大部分针对的都是理想欧氏空间.而在真实的情况下,反k最近邻查询通常受障碍物影响.文中研究了障碍空间中反k最近邻查询算法,提出了一种基于障碍Voronoi图的高效的剪枝方法.根据Voronoi图和障碍距离的特性,大幅度减少了数据点处理个数.最后,作者使用真实的数据集和多种方式分布的模拟数据,验证了算法的高效性和准确性.