空间数据库中的障碍反向最近邻查询

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (34): 130-133.

• 数据库、信号与信息处理 • 上一篇下一篇

空间数据库中的障碍反向最近邻查询

杨泽雪1，3，郝忠孝1，2

1.哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080
2.哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001
3.黑龙江工程学院计算机科学与技术系，哈尔滨 150050

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-12-01 发布日期:2011-12-01

Obstructed reverse nearest neighbor queries in spatial databases

YANG Zexue1，3，HAO Zhongxiao1，2

1.College of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China
2.College of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China
3.Department of Computer Science and Technology，Heilongjiang Institute of Technology，Harbin 150050，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-12-01 Published:2011-12-01

摘要/Abstract

摘要： 反向最近邻查询已成为空间查询的热点问题，而障碍物在实际应用中是不可避免的，因而在障碍物环境中的反向最近邻查询也成为重要的空间查询。已有的可视反向最近邻查询只考虑了可视性，并没有考虑最小障碍距离。提出一种障碍物环境中新的反向最近邻查询的变体，查找障碍距离最小的反向最近邻，即障碍反向最近邻查询。利用障碍距离的计算和相应的剪枝规则，给出障碍反向最近邻查询的算法及相关定理和证明。

关键词: 反向最近邻, 空间数据库, 可视性, 障碍距离

Abstract: Reverse Nearest Neighbor（RNN） query has been a hot subject of spatial query.In the real world，obstacles are not avoided，so the RNN query which considers the obstacle existed has become an important spatial query.The existed visible RNN only considers the visibility and does not take obstructed distance into consideration.This paper introduces a novel variant of RNN queries，the Obstructed Reverse Nearest Neighbor（ORNN） search，which finds the RNN with the shortest obstructed distance among the obstacles.By using the computation of obstructed distance and the related pruning heuristics，the ORNN query processing algorithm is proposed，and the relevant theorem and proof are given.

Key words: Reverse Nearest Neighbor（RNN）, spatial database, visibility, obstructed distance

杨泽雪1，3，郝忠孝1，2. 空间数据库中的障碍反向最近邻查询[J]. 计算机工程与应用, 2011, 47(34): 130-133.

YANG Zexue1，3，HAO Zhongxiao1，2. Obstructed reverse nearest neighbor queries in spatial databases[J]. Computer Engineering and Applications, 2011, 47(34): 130-133.

[1]	周永望1，2，吴超辉3，张涵斐1. 城市作战环境中可视性算法研究及模型构建[J]. 计算机工程与应用, 2018, 54(6): 210-215.
[2]	杨泽雪. 空间数据库中的一种混合索引结构的研究[J]. 计算机工程与应用, 2017, 53(20): 20-23.
[3]	周屹1，杨泽雪1，2. 空间数据库中的线段k近邻查询研究[J]. 计算机工程与应用, 2015, 51(18): 131-134.
[4]	张丽平1，李松1，郝晓红2，郝忠孝1. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.
[5]	徐红波1，2，姚念民2，韩启龙2，潘海为2. 支持线段查询索引结构CB树[J]. 计算机工程与应用, 2015, 51(11): 114-118.
[6]	肖邱勇，李光强. 空间数据库性能对比实验分析[J]. 计算机工程与应用, 2014, 50(21): 139-142.
[7]	吴超辉1，张涵斐2，公茂玉1. 从外存中计算地形可视域的高效算法[J]. 计算机工程与应用, 2014, 50(12): 48-53.
[8]	林键，刘仁义，刘南，张丰. 基于查询优化器的分布式空间查询优化方法[J]. 计算机工程与应用, 2012, 48(22): 161-165.
[9]	张丽平，李松，郝忠孝. 球面上的最近邻查询方法研究[J]. 计算机工程与应用, 2011, 47(5): 126-129.
[10]	李进，余建桥. 空间对象的反最近邻查询处理技术研究[J]. 计算机工程与应用, 2011, 47(33): 146-148.
[11]	徐红波1，韩启龙2，潘海为2. 空间数据库最优位置查询算法研究[J]. 计算机工程与应用, 2011, 47(18): 19-21.
[12]	邹永贵，徐海波，梁新发，杨富平. 一种优化的空间连接算法[J]. 计算机工程与应用, 2011, 47(12): 117-121.
[13]	曹泽文，谭川豫，王晓辉. 移动对象反向最近邻查询处理技术研究进展[J]. 计算机工程与应用, 2011, 47(10): 138-141.
[14]	董军,杨秀娟. 移动对象的动态反向k最近邻研究[J]. 计算机工程与应用, 2009, 45(6): 155-157.
[15]	谭新莲¹，武凤翔²，陆彦辉¹. 进化蚁群优化理论实现障碍距离分析[J]. 计算机工程与应用, 2009, 45(22): 224-227.

空间数据库中的障碍反向最近邻查询

Obstructed reverse nearest neighbor queries in spatial databases

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics