Computer Science ›› 2018, Vol. 45 ›› Issue (6): 172-175.doi: 10.11896/j.issn.1002-137X.2018.06.030

• Software & Database Technology • Previous Articles     Next Articles

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

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: Spatial database, Line segment obstruction distance, OLGNN, Voronoi diagram of line segment

CLC Number: 

  • 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] LI Song,ZHANG Li-ping,ZHU De-long and HAO Xiao-hong. Simple Continues Near Neighbor Chain Query in Dynamic Constrained Regions [J]. Computer Science, 2014, 41(6): 136-141.
[2] HOU Shi-jiang,ZHANG Yu-jiang and LIU Guo-hua. Spatial K-Anonymity Reciprocal Algorithm Based on Locality-sensitive Hashing Partition [J]. Computer Science, 2013, 40(8): 115-118.
[3] . Line Segment Closest Pair Queries Based on Voronoi Diagram [J]. Computer Science, 2012, 39(6): 143-146.
[4] XU Cheng-zhi,Phillip SHEU Chen-yu,QIAN Tie-yun. New Spatial Query Language Based on GIS [J]. Computer Science, 2010, 37(6): 206-210.
[5] SONG Guang-jun,HAO Zhong-xiao,WANG Li-jie. Indexing of Moving Objects in a Constrained Network [J]. Computer Science, 2009, 36(12): 138-141.
[6] . [J]. Computer Science, 2007, 34(10): 149-151.
[7] LIU Xiao-Feng, LIU Yun-Sheng ,XIAO Yin-Yuan (School of Computer Science and Technology, Huazhong University of Science and Teehnology,Wuhan 430074). [J]. Computer Science, 2006, 33(5): 156-158.
[8] LIU Yun-Sheng,LIU Xiao-Feng,XIAO Yin-Yuan (School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074). [J]. Computer Science, 2005, 32(9): 108-110.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .