计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 172-175.doi: 10.11896/j.issn.1002-137X.2018.06.030
郭莹莹, 张丽平, 李松
GUO Ying-ying, ZHANG Li-ping, LI Song
摘要: 为了解决现有成果无法有效处理障碍环境下的线段组最近邻查询问题,提出了障碍环境中线段组最近邻查询方法。查询过程分为过滤阶段和精炼阶段两个部分。在过滤过程中,首先根据线段Voronoi图的性质以及线段障碍组最近邻查询的定义,提出了针对数据线段的剪枝定理,并提出了OLGNN_Line_Filter算法;根据线段障碍距离的定义,进一步提出针对障碍物的剪枝定理,并给出了OLGNN_Obstacle_Filter算法。在精炼过程中,为了得到更精确的查询结果,提出了相应的精炼定理和精炼算法STA_OLGNN。理论研究和实验表明,所提算法能够有效地处理障碍环境下的线段组最近邻查询问题。
中图分类号:
[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. |
|