计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 172-175.doi: 10.11896/j.issn.1002-137X.2018.06.030

• 软件与数据库技术 • 上一篇    下一篇

障碍环境中线段组最近邻查询方法研究

郭莹莹, 张丽平, 李松   

  1. 哈尔滨理工大学计算机科学与技术学院 哈尔滨150080
  • 收稿日期:2017-04-27 出版日期:2018-06-15 发布日期:2018-07-24
  • 作者简介:郭莹莹(1993-),女,硕士生,CCF会员,主要研究方向为数据挖掘、数据查询;张丽平(1976-),女,硕士,副教授,CCF会员,主要研究方向为数据结构和算法设计、数据库,E-mail:zhangliping@0703@163.com(通信作者);李 松(1977-),男,博士,副教授,CCF会员,主要研究方向为空间数据查询与处理、算法设计
  • 基金资助:
    本文受黑龙江省教育厅科学技术研究项目(12531z004)资助

Group Nearest Neighbor Query Method of Line Segment in Obstacle Space

GUO Ying-ying, ZHANG Li-ping, LI Song   

  1. School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
  • Received:2017-04-27 Online:2018-06-15 Published:2018-07-24

摘要: 为了解决现有成果无法有效处理障碍环境下的线段组最近邻查询问题,提出了障碍环境中线段组最近邻查询方法。查询过程分为过滤阶段和精炼阶段两个部分。在过滤过程中,首先根据线段Voronoi图的性质以及线段障碍组最近邻查询的定义,提出了针对数据线段的剪枝定理,并提出了OLGNN_Line_Filter算法;根据线段障碍距离的定义,进一步提出针对障碍物的剪枝定理,并给出了OLGNN_Obstacle_Filter算法。在精炼过程中,为了得到更精确的查询结果,提出了相应的精炼定理和精炼算法STA_OLGNN。理论研究和实验表明,所提算法能够有效地处理障碍环境下的线段组最近邻查询问题。

关键词: 空间数据库, 线段Voronoi图, 线段障碍距离, 线段障碍组最近邻

Abstract: In order to make up the deficiencies of the existing research results which can not effectively deal with the group nearest neighbor query based on line segment in obstacle space,the group nearest neighbor query method of line segment in obstacle space was proposed.This query process is divided into two stages,including the filtering process and refining process.In the filtering process,according to the properties of the line segment Voronoi graph and the definition of OLGNN,corresponding pruning theorem of data line was proposed,and the OLGNN_Line_Filter algorithm was put forward.According to the definition of line obstruction distance,corresponding pruning theorem of obstruction was proposed,and the OLGNN_Obstacle_Filter algorithm was put forward.In the refining process,in order to get more accurate query results,the corresponding refining theorem and STA_OLGNN algorithm were proposed.Theoretical research and experimental results show that the proposed algorithm can effectively deal with the problem of group nearest neighbor query of line segment in obstacle environment.

Key words: Line segment obstruction distance, OLGNN, Spatial database, Voronoi diagram of line segment

中图分类号: 

  • TPP31.13
[1]ROUMELIS G,VASSILAKOPOULOS M,CORRAL A,et al.Plane-sweep algorithms for the k group nearest-neighbor query[C]//International Conference on Geographical Information Systems Theory,Applications and Management.2015:83-93.
[2]SON W,BAE S W,AHN H K.Group nearest-neighbor queries in the L 1 plane[J].Theoretical Computer Science,2015,592(C):39-48.
[3]ZHANG L P,ZHAO J Q,LI S,et al.Research on Methods of Construction of Voronoi Diagram and Nearest Neighbor Query in Constrained Regions[J].Computer Science,2014,41(9):220-224.(in Chinese)
张丽平,赵纪桥,李松,等.Voronoi图的构建与受限区域内的最近邻查询方法研究[J].计算机科学,2014,41(9):220-224.
[4]NURAIN N,ALI M E,HASHEM T,et al.Group nearest neighbor queries for fuzzy geo-spatial objects[C]//International ACM Workshop on Managing and Mining Enriched Geo-Spatial Data.New York:ACM,2015:25-30.
[5]CHEN M,JIA Z X,GU Y,et al.Group nearest neighbor queries over existentially uncertain data[J].Journal of ChineseCompu-ter Systems,2012,33(4):684-687.(in Chinese)
陈默,贾子熙,谷峪,等.面向存在不确定对象的组最近邻查询方法[J].小型微型计算机系统,2012,33(4):684-687.
[6]HASHEM T,ALI M E,KULIK L,et al.Protecting privacy for group nearest neighbor queries with crowd sourced data and computing[C]//2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing,Zurich,Switzerland,2013.New York,NY,USA:ACM,2013:559-562.
[7]YU X N,GU Y,ZHANG T C,et al.A method for reverse k-nearest neighbor queries in obstructed spaces[J].Chinese Journal of Computers,2011,34(10):1917-1925.(in Chinese)
于晓楠,谷峪,张天成,等.一种障碍空间中的反k最近邻查询方法[J].计算机学报,2011,34(10):1917-1925.
[8]ZHU H J,WANG J J,WANG B,et al.Location privacy pressing obstructed nearest neighbor queries[J].Journal of Computer Research and Development,2014,51(1):115-125.
[9]ZHU H,YANG X,WANG B,et al.Range-based obstructed nearest neighbor queries[C]//2016 International Conference on Management of Data (SIGMOD’16),San Francisco,California,USA,2016.New York,NY,USA:ACM,2016:2053-2068.
[10]HAO Z X,WANG Y D,HE Y B.Line segment nearest neighbor query of spatial database[J].Journal of Computer Research and Development,2008,45(9):1539-1545.(in Chinese)
郝忠孝,王玉东,何云斌.空间数据库平面线段最近邻查询问题研究[J].计算机研究与发展,2008,45(9):1539-1545.
[11]LIU R T,HAO Z X.Fast algorithm of nearest neighbor query for line segments of spatial database[J].Journal of Computer Research and Development,2011,48(12):2379-2384.(in Chinese)
刘润涛,郝忠孝.空间数据库平面线段快速最近邻查询算法[J].计算机研究与发展,2011,48(12):2379-2384.
[12]ZHOU Y,YANG Z X.Research on line segment kNN query in spatial database[J].Computer Engineering and Applications,2015,51(18):131-134.(in Chinese)
周屹,杨泽雪.空间数据库中的线段k近邻查询研究[J].计算机工程与应用,2015,51(18):131-134.
[13]GU Y,ZHANG H,WANG Z,et al.Efficient moving k nearest neighbor queries over line segment objects[J].World Wide Web,2016,19(4):653-677.
[14]PAPADOPOULOU E,ZAVERSHYNSKYI M.The higher-order Voronoi diagram of line segments[J].Algorithmica,2014,74(1):1-25.
[15]Dataset[EB/OL].http://konect.uni-koblenz.de/networks/roadNet-CA,2016.
[1] 李松,张丽平,朱德龙,郝晓红.
动态受限区域内的单纯型连续近邻链查询方法
Simple Continues Near Neighbor Chain Query in Dynamic Constrained Regions
计算机科学, 2014, 41(6): 136-141. https://doi.org/10.11896/j.issn.1002-137X.2014.06.027
[2] 侯士江,张玉江,刘国华.
基于位置敏感哈希分割的空间K-匿名共匿算法
Spatial K-Anonymity Reciprocal Algorithm Based on Locality-sensitive Hashing Partition
计算机科学, 2013, 40(8): 115-118.
[3] 杨泽雪,郝忠孝.
基于Voronoi图的线段最近对查询
Line Segment Closest Pair Queries Based on Voronoi Diagram
计算机科学, 2012, 39(6): 143-146.
[4] 徐承志,许承瑜,钱铁云.
基于GIS系统的空间查询语言
New Spatial Query Language Based on GIS
计算机科学, 2010, 37(6): 206-210.
[5] 邹志文,陈昌乾,鞠时光.
带空间特性的角色访问控制研究
Research on Role-based Access Control with Spatial Character
计算机科学, 2010, 37(1): 189-191.
[6] .
空间数据库管理系统VISTA的强制访问控制设计

计算机科学, 2007, 34(10): 149-151.
[7] 刘小峰 刘云生 肖迎元.
空间数据库中约束K最接近对查询

计算机科学, 2006, 33(5): 156-158.
[8] 刘云生 刘小峰 肖迎元.
空间数据库中最小距离聚集查询及其算法

计算机科学, 2005, 32(9): 108-110.
[9] 刘永山 郝忠孝.
基于矩阵的原子方向关系合成

计算机科学, 2005, 32(5): 101-104.
[10] 涂小朋 汪林林.
分布式空间数据库中基于事务的客户端高速缓存技术研究

计算机科学, 2004, 31(6): 76-78.
[11] 郑志强 吴春明 余建桥.
空间数据概念树提升算法研究

计算机科学, 2004, 31(4): 120-122.
[12] 李琦 常磊 王凌云.
面向数字城市的空间数据库设计与实现

计算机科学, 2004, 31(3): 89-91.
[13] 何彬彬 方涛 郭达志.
基于不确定性的空间聚类

计算机科学, 2004, 31(11): 196-198.
[14] 肖予钦 景宁 吴秋云 钟志农.
空间数据挖掘关键问题研究

计算机科学, 2003, 30(9): 49-53.
[15] 范建伟 汪林林.
空间数据库磁盘管理器的研究与设计

计算机科学, 2003, 30(6): 93-95.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!