障碍环境中可视反向视域K最近邻查询

doi:10.19678/j.issn.1000-3428.0064280

计算机工程 ›› 2022, Vol. 48 ›› Issue (8): 258-265. doi: 10.19678/j.issn.1000-3428.0064280

障碍环境中可视反向视域K最近邻查询

杨泽雪^1,2,3, 王阿川¹, 李陆³, 李松⁴

1. 东北林业大学信息与计算机工程学院, 哈尔滨 150040;
2. 黑龙江工程学院计算机科学与技术系, 哈尔滨 150050;
3. 黑龙江省政务大数据中心, 哈尔滨 150028;
4. 哈尔滨理工大学计算机科学与技术学院, 哈尔滨 150080

收稿日期:2022-03-23 修回日期:2022-05-05 发布日期:2022-08-09
作者简介:杨泽雪(1978-),女,副教授、博士后,主研方向为空间数据库、空间查询;王阿川,教授,博士生导师;李陆,高级工程师,硕士;李松,教授、博士。
基金资助:
中国博士后科学基金（2019M651318）；黑龙江省自然科学基金（LH2020F047）；黑龙江省高等教育教学改革重点委托项目（SJGZ20200145）；黑龙江工程学院创新团队项目（2020CX07）。

Visible Reverse View Field K-Nearest Neighbor Queries in Obstacle Environment

YANG Zexue^1,2,3, WANG Achuan¹, LI Lu³, LI Song⁴

1. College of Information and Computer Engineering, Northeast Forestry University, Harbin 150040, China;
2. Department of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin 150050, China;
3. Heilongjiang Provincial Big Data Center of Government Affairs, Harbin 150028, China;
4. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China

Received:2022-03-23 Revised:2022-05-05 Published:2022-08-09

摘要/Abstract

摘要： 在障碍环境下的空间应用中，用户通常只对视域范围内可视的数据对象感兴趣。为解决障碍环境中视域范围内的反向最近邻查询问题，将视域可视性引入到反向K最近邻查询中，提出一种可视反向视域K最近邻查询算法。给定某空间数据集P、障碍集O和查询点q，可视反向视域K最近邻查询检索P中数据点，并将q作为可视视域K最近邻。应用查询点进行障碍过滤，得到障碍过滤算法，利用数据对象的视域进行剪枝，使用查询点与数据对象的关系剪枝，形成有效的障碍剪枝规则，并根据剪枝规则得到视域可视性判断算法。在此基础上，分别基于R^*-树和VFR-树提出可视反向视域K最近邻查询算法R^*-V2-RKNN和VFR-V2-RKNN，并分别通过对R^*-树和VFR-树进行一次遍历得到查询结果。在真实数据集和模拟数据集上的实验结果表明，VFR-V2-RKNN算法的查询性能明显优于R^*-V2-RKNN算法。

关键词: 障碍, 可视性, 视域, 反向K最近邻查询, 空间查询

Abstract: In spatial applications used in obstacle environments, users are usually only interested in visible data objects within the field of view.To solve the problem of a reverse nearest-neighbor query within the field of view in an obstacle environment, view field visibility is introduced into the Reverse K-Nearest Neighbor(RKNN) query, and a Visible Reverse View Field K-Nearest Neighbor (V2-RKNN) query algorithm is proposed.The query considers both the visibility and view field, which makes up for the deficiency in which the existing query only considers one aspect.Given a spatial data set P, an obstacle set O, and a query point q, the V2-RKNN query retrieves the data points in P that have q as their visible view field K-nearest neighbor.First, a query point is used for obstacle filtering to obtain the obstacle filtering algorithm.The view field of the data object is then used for pruning, and the relationship between the query point and data object is applied to the pruning to form effective obstacle pruning rules, based upon which a view field visibility judgment algorithm is achieved.On this basis, two visible reverse view field K nearest neighbor algorithms, R^*-V2-RKNN and VFR-V2-RKNN, based on an R^*-tree and VFR-tree, respectively, are developed.The two algorithms obtain their query results through one traversal of an R^*-tree and VFR-tree, respectively, and the query efficiency of the VFR-V2-RKNN algorithm is verified experimentally on real and synthetic data sets.

Key words: obstacle, visibility, view field, Reverse K-Nearest Neighbor(RKNN) query, spatial query

中图分类号:

TP391

杨泽雪, 王阿川, 李陆, 李松. 障碍环境中可视反向视域K最近邻查询[J]. 计算机工程, 2022, 48(8): 258-265.

YANG Zexue, WANG Achuan, LI Lu, LI Song. Visible Reverse View Field K-Nearest Neighbor Queries in Obstacle Environment[J]. Computer Engineering, 2022, 48(8): 258-265.

http://www.ecice06.com/CN/Y2022/V48/I8/258

图/表 14

20220825093754

20220825093757

20220825093801

20220825093804

20220825093808

20220825093851

20220825093920

20220825093924

20220825093928

20220825093931

20220825093935

20220825093939

20220825093942

20220825093946

参考文献

[1] TAO Y F, PAPADIAS D, LIAN X.K-Reverse NN search in arbitrary dimensionality[C]//Proceedings of 2004 VLDB Conference.Amsterdam:USA Elsevier, 2004:744-755.
[2] GOTOH Y, OKUBO C.A searching method for bichromatic reverse k-nearest neighbor with network voronoi diagram[C]//Proceedings of the 14th International Conference on Advances in Mobile Computing and Multi Media.Singapore Singapore.New York, USA:ACM Press, 2016:71-78.
[3] ALLHEEIB N, ADHINUGRAHA K, TANIAR D, et al.Computing reverse nearest neighbourhood on road maps[J].World Wide Web, 2022, 25(1):99-130.
[4] XU J K, ZHAO Y D, YU G.An evaluation and query algorithm for the influence of spatial location based on RKNN[J].Frontiers of Computer Science, 2020, 15(2):1-9.
[5] BENETIS R, JENSEN C S, KARCIAUSKAS G, et al.Nearest neighbor and reverse nearest neighbor queries for moving objects[C]//Proceedings of International Database Engineering and Applications Symposium.Washington D.C., USA:IEEE Press, 2002:44-53.
[6] KANG J M, MOKBEL M F, SHEKHAR S, et al.Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors[C]//Proceedings of the 23rd International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2007:806-815.
[7] CHEONG O, VIGNERON A, YON J.Reverse nearest neighbor queries in fixed dimension[J].International Journal of Computational Geometry &Applications, 2011, 21(2):179-188.
[8] ACHTERT E, BÖHM C, KRÖGER P, et al.Approximate reverse k-nearest neighbor queries in general metric spaces[C]//Proceedings of the 15th ACM International Conference on Information and Knowledge Management.New York, USA:ACM Press, 2006:788-789.
[9] LIN J, ETTER D, DEBARR D.Exact and approximate reverse nearest neighbor search for multimedia data[C]//Proceedings of 2008 SIAM International Conference on Data Mining.Philadelphia, PA:Society for Industrial and Applied Mathematics, 2008:656-667.
[10] FRANCISCO G, CORRAL A, IRIBARNE L, et al.RKNN query processing in distributed spatial infrastructures:a performance study[C]//Proceedings of International Conference on Model and Data Engineering.Berlin, Germany:Springer, 2017:200-207.
[11] GARCIA F, F, CORRAL A, IRIBARNE L, et al.MRSLICE:efficient RKNN query processing in spatial hadoop[C]//Proceedings of International Conference on Model and Data Engineering.Berlin, Germany:Springer, 2019:235-250.
[12] LI X G, XIANG T, GUO S W, et al.Privacy-preserving reverse nearest neighbor query over encrypted spatial data[J].IEEE Transactions on Services Computing, 2021:1:1-15.
[13] PAN X, NIE S L, HU H B, et al.Reverse nearest neighbor search in semantic trajectories for location-based services[J].IEEE Transactions on Services Computing, 2022, 15(2):986-999.
[14] BUCCAFURRI F, LAX G, NICOLAZZO S, et al.A privacy-preserving localization service for assisted living facilities[J].IEEE Transactions on Services Computing, 2020, 13(1):16-29.
[15] NUTANONG S, TANIN E, ZHANG R.Visible nearest neighbor queries[C]//Proceedings of International Conference on Database Systems for Advanced Applications.Berlin, Germany:Springer, 2007:876-883.
[16] NUTANONG S, E T N, RUI Z.Incremental evaluation of visible nearest neighbor queries[J].IEEE Transactions on Knowledge and Data Engineering, 2010, 22(5):665-681.
[17] GAO Y J, ZHENG B H, CHEN G C, et al.Continuous visible nearest neighbor query processing in spatial databases[J].The VLDB Journal, 2011, 20(3):371-396.
[18] WANG Y Q, ZHANG R, XU C F, et al.Continuous visible k nearest neighbor query on moving objects[J].Information Systems, 2014, 44:1-21.
[19] XU H, LI Z C, LU Y S, et al.Group visible nearest neighbor queries in spatial databases[C]//Proceedings of the 11th International Conference on Web-Age Information Management.Berlin, Germany:Springer, 2010:333-344.
[20] GAO Y J, ZHENG B H, CHEN G C, et al.Visible reverse k-nearest neighbor query processing in spatial databases[J].IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9):1314-1327.
[21] 杨泽雪, 郝忠孝.空间数据库中连续可视反向最近邻查询[J].西南交通大学学报, 2012, 47(3):451-457. YANG Z X, HAO Z X.Continuous visible reverse nearest neighbor queries in spatial databases[J].Journal of Southwest Jiaotong University, 2012, 47(3):451-457.(in Chinese)
[22] LIU Y S, KONG D H.Continuous visible query for three-dimensional objects in spatial databases[J].Mathematical Problems in Engineering, 2016(8):1-12.
[23] YI S, RYU H, SON J, et al.View field nearest neighbor:a novel type of spatial queries[J].Information Sciences, 2014, 275:68-82.
[24] KIM W, SHIM C, HEO W, et al.Moving view field nearest neighbor queries[J].Data &Knowledge Engineering, 2019, 119:58-70.
[25] YI S, SHIM C, CHUNG Y D.Reverse view field nearest neighbor queries[J].Information Sciences, 2017, 402:35-49.
[26] SU I F, CHEN D L, LEE C A, et al.Finding visible kNN objects in the presence of obstacles within the user's view field[J].ISPRS International Journal of Geo-Information, 2019, 8(3):151-159.

选择文件类型/文献管理软件名称

选择包含的内容

障碍环境中可视反向视域K最近邻查询

Visible Reverse View Field K-Nearest Neighbor Queries in Obstacle Environment

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陆昭吾, 王骏, 施俊. 面向自闭症辅助诊断的深度对比模糊神经网络[J]. 计算机工程, 2023, 49(4): 263-271.
[2]	宁小娟, 巩亮, 张金磊. 基于激光点云的道路可通行区域检测方法[J]. 计算机工程, 2022, 48(4): 22-29.
[3]	汪佩,郭剑辉,李伦波,赵春霞. 基于单线激光雷达与视觉融合的负障碍检测算法[J]. 计算机工程, 2017, 43(7): 303-308.
[4]	李松,张丽平,刘艳,郝晓红,杨和禹. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
[5]	杨泽雪，郝忠孝. 基于Voronoi图的连续反向最近邻查询[J]. 计算机工程, 2014, 40(1): 272-274,279.
[6]	范协裕，任应超，邓富亮，王庆刚. 基于代理的并行空间查询语言[J]. 计算机工程, 2013, 39(11): 61-64.
[7]	梁金泉, 周之平, 黎明, 万国. 基于关键链遗传操作的机器人路径规划[J]. 计算机工程, 2012, 38(9): 166-169.
[8]	黄叶珏, 褚一平. 基于超复视域注意模型的视频分割算法[J]. 计算机工程, 2012, 38(14): 217-219.
[9]	孙冬璞, 郝忠孝. 基于障碍物群的k全局相异最优有序路径查询[J]. 计算机工程, 2011, 37(5): 80-82.
[10]	刘艳, 郝忠孝. 高维主存的反向K最近邻查询及连接[J]. 计算机工程, 2011, 37(24): 22-24.
[11]	彭勤生;方金云;张娟. 基于空间和属性数据的联合索引技术[J]. 计算机工程, 2010, 36(8): 71-73.
[12]	陈智鹏, 杨诗琴. 带障碍物情况下两点间最短距离的求解方法[J]. 计算机工程, 2010, 36(16): 171-173.
[13]	蔡龙, 马秀丽, 张开翼, 万旺根. 基于可见性裁剪的地形数据流式传输策略[J]. 计算机工程, 2010, 36(13): 283-285.
[14]	沈志熙;黄席樾;杨镇宇;韦金明. 基于Boosting的智能车辆多类障碍物识别[J]. 计算机工程, 2009, 35(14): 241-242.
[15]	刘天孚;程如意. 基于遗传算法的移动机器人路径规划[J]. 计算机工程, 2008, 34(17): 214-215.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

障碍环境中可视反向视域K最近邻查询

Visible Reverse View Field K-Nearest Neighbor Queries in Obstacle Environment

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献

相关文章 15

编辑推荐

Metrics

本文评价