Computer Science ›› 2016, Vol. 43 ›› Issue (5): 174-178.doi: 10.11896/j.issn.1002-137X.2016.05.032

Previous Articles     Next Articles

k Nearest Neighbor Query Based on Voronoi Diagram for Obstructed Spaces

ZHANG Li-ping, JING Hai-dong, LI Song and CUI Huan-yu   

  • Online:2018-12-01 Published:2018-12-01

Abstract: In order to enhance the efficiency of k nearest neighbor in obstructed spaces,k nearest neighbor query method based on Voronoi diagram in obstructed spaces was studied,and kNN-Obs algorithm based on Voronoi diagram in obstructed spaces was proposed.This algorithm adopts two processes:filtration and refinement.Filtration mainly uses the filter function of Voronoi diagram and largely reduces the number of query points.Refinement mainly screens objects within the candidate set according to barrier distance and Voronoi neighbor.And further ADDkNN-Obs algorithm for newly-added points and DENkNN-Obs algorithm for deleted points were given.The experiment shows that the algorithm has advantages in dealing with the k nearest neighbor problem in obstructed spaces.

Key words: Voronoi diagram,k nearest neighbor query,Obstructed spaces,Obstructed distance

[1] 郝忠孝.时空数据库查询与推理[M].北京:科学出版社,2010
[2] 李松,张丽平,孙冬璞.空间关系查询与分析[M].哈尔滨:哈尔滨工业大学出版社,2011
[3] Sacl J R,Urrutia J.Vorouoi diagrams.handbook ou computa-tioual geometry[M].Ottawa:Elsevier Science,2000:201-290
[4] Jegou H,Inria R,Schmid C.Product Quantization for NearestNeighbor Search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,3(1):117-128
[5] Geng Zhao,Xuan K F,Johanna R,et al.VIC.Voronoi-BasedContinuous k Nearest Neighbor Search in Mobile Navigation[J].IEEE Transactions on Industrial Electronics,2011,58(6):2247-2257
[6] Esmaeili M M,Ward R K,Fatourechi M.A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012:2481-2488
[7] Zheng Li-gang,Qiu Guo-ping,Huang Ji-wu,et al.Fast and accurate Nearest Neighbor search in the manifolds of symmetric po-sitive definite matrices[C]∥Acoustics,Speech and Signal Processing.2014:3804-3808
[8] Zhang Li-ping,Zhao Ji-qiao,Li Song,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,247(in Chinese) 张丽平,赵纪桥,李松,等.Voronoi图的构建与受限区域内的最近邻查询方法研究[J].计算机科学,2014,41(9):220-224,247
[9] Yuan P S,Sha C F,Wang X L,et al.c-Approximate nearest neighbor query algorithm based on learning for high-dimensional data[J].Journal of Software,2012,23(8):2018-2031(in Chinese) 袁培森,沙朝锋,王晓玲,等.一种基于学习的高维数据c-近似最近邻查询算法[J].软件学报,2012,23(8):2018-2031
[10] Lu Yan-sheng,He Ya-jun,Pan Peng.Improvement of the EINN Algorithm for NN Query Traversing[J].Computer Engineering and Science,2005,27(7):62-64(in Chinese) 卢炎生,何亚军,潘鹏.EINN最近邻居查询索引遍历算法改进[J].计算机工程与科学,2005,27(7):62-64
[11] Li Song,Zhang Li-ping.Simple Continues Near Neighbor Chain Query in Dynamic Constrained Regions[J].Computer Science,2014,41(6):136-141(in Chinese) 李松,张丽平.动态受限区域内的单纯型连续近邻链查询方法[J].计算机科学,2014,41(6):136-141
[12] Gao Y,Zheng B.Continuous obstructed nearest neighbor queries in spatial databases[C]∥Proceedings of the 28th ACM SIGMOD International Conference of Management of Data(Sigmod’ 09).New York,USA,2009:577-590
[13] Nutanong S,Tanin E,Zhang Rui.Incremental evaluation of visible nearest neighbor queries[J].IEEE Transactions on Know-ledge Engineering,2010,22(5):665-681
[14] Gao Y,Yang J C,Chen G,et al.On efficient obstructed reverse nearest neighbor query processing[C]∥Proc.of the 19th Int’l Conf.on Advances in Geographic Information Systems.Chicago:ACM Press,2011:191-120
[15] Li Chuan-wen,Gu Yu,Qi Jian-zhong,et al.A safe region based approach to moving KNN queries in obstructed space[J].Knowledge and Information Systems,2014,24(3):179-195
[16] Wang Yan-qiu,Zhang Rui,Xu Chuan-fei,et al.Continuous visible k nearest neighbor query on moving objects[J].Information Systems,2014,44(8):1-21
[17] Yu Xiao-nan,Gu Yu,Zhang Tian-cheng,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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!