移动对象的反向k近邻查询算法的研究

J4 ›› 2013, Vol. 35 ›› Issue (1): 149-154.

移动对象的反向k近邻查询算法的研究

许凯,杨萌

（河海大学计算机与信息学院，江苏南京 210098;南京工业大学，江苏南京 210009）

收稿日期:2011-11-08 修回日期:2012-02-20 出版日期:2013-01-25 发布日期:2013-01-25

Algorithm research on continuous reverseknearestneighbor query for spatial moving objects

XU Kai,YANG Meng

(Department of Computer and Information Engineering,Hohai University,Nanjing 210098;
Nanjing University of Technology,Nanjing 210009,China)

Received:2011-11-08 Revised:2012-02-20 Online:2013-01-25 Published:2013-01-25

摘要/Abstract

摘要：

传统的反向k近邻查询的研究主要集中在k=1时的单色移动对象的反向最近邻查询上，单色和双色的反向k近邻查询问题还没有解决。利用网格索引结构结合60°平面修剪策略，提出了一种解决单色和双色的移动对象的连续反向k近邻查询方法。最后实验结果验证了算法的有效性。

关键词: 反向最近邻, 连续最近邻, 网格索引, 范围查询

Abstract:

There have been no proposals for answering monochromatic and bichromatic RkNN queries problems for continuously moving objects, while the traditional algorithms focus on monochromatic RkNN query for moving objects. This paper proposes an algorithm using the grid index combined with 60° pruning strategy to realize monochromatic and bichromatic RkNN queries for continuously moving objects. Experimental results demonstrate the effectiveness of the proposed algorithm.

Key words: reverse nearest neighbor;continuous nearest neighbor;grid index;range query

许凯,杨萌. 移动对象的反向k近邻查询算法的研究[J]. J4, 2013, 35(1): 149-154.

XU Kai,YANG Meng. Algorithm research on continuous reverseknearestneighbor query for spatial moving objects[J]. J4, 2013, 35(1): 149-154.

[1]	王波涛，赵凯利，常立东，李睿，黄山，李静，李响. 基于Storm的连续范围查询优化技术[J]. 计算机工程与科学, 2017, 39(01): 1-14.
[2]	张晓琳,郭丹丹,郝琨. 一种适用连续不确定XML数据的索引[J]. J4, 2016, 38(02): 305-311.
[3]	甘亮1,2,于莉莉3,李润恒1,贾焰1,金鑫4. 一种基于逆支配点集的数据流Top-k计算方法[J]. J4, 2012, 34(6): 59-64.
[4]	李楠1，吴信才2，马金金3，王中. 基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法[J]. J4, 2012, 34(11): 96-103.
[5]	张丽，邹鹏，贾焰. 基于网格的数据流连续约束Skyline处理技术研究[J]. J4, 2011, 33(8): 173-180.
[6]	田李李爱平邹鹏贾焰. 更新数据流上的连续Skyline计算[J]. J4, 2008, 30(5): 59-64.
[7]	吴永英张吉根李晨阳. 金字塔多维索引分析及其算法实现[J]. J4, 2006, 28(10): 92-94.