计算机科学 ›› 2016, Vol. 43 ›› Issue (5): 174-178.doi: 10.11896/j.issn.1002-137X.2016.05.032
张丽平,经海东,李松,崔环宇
ZHANG Li-ping, JING Hai-dong, LI Song and CUI Huan-yu
摘要： 为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。
| [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! |
|
||
首页