计算机科学 ›› 2014, Vol. 41 ›› Issue (9): 220-224.doi: 10.11896/j.issn.1002-137X.2014.09.041
张丽平,赵纪桥,李松,经海东,崔环宇
ZHANG Li-ping,ZHAO Ji-qiao,LI Song,JING Hai-dong and CUI Huan-yu
摘要: Voronoi图在空间数据查询、数据挖掘、图像处理、模式识别和智能交通管理等方面具有重要的作用。为了简化构建的复杂性和提高构建效率,基于分治法、启发式局部优化策略和局部数据点的扫描线动态更新策略,提出了基于凸包的Voronoi图生成方法,给出了Create_Voronoi()算法。进一步,为了弥补已有近邻查询方法无法处理受限区域内的最近邻查询的不足,基于Voronoi图研究了受限区域内的同质和异质最近邻查询方法,分别提出了TVor_NN()算法和YVor_NN()算法。理论研究和实验分析表明,提出的研究方法在Voronoi图的构建和受限范围的最近邻查询等方面具有较大的优势。
[1] 郝忠孝.时空数据库查询与推理[M].北京:科学出版社,2010 [2] 李松,张丽平,孙冬璞.空间关系查询与分析[M].哈尔滨:哈尔滨工业大学出版社,2011 [3] Sacl J R,Urrutia J.Voronoi diagrams.handbook on computa-tional geometry[M].Ottawa:Elsevier Science,2006:201-290 [4] Dong L,Wu Y,Zhou S.Constructing the Voronoi Diagram of Planar Point Set in Parallel[C]∥International Conference on Computational Intelligence and Software Engineering,2009(CiSE 2009).IEEE,2009:1-5 [5] 张娟,杜全叶.增删点后的Voronoi图生成算法[J].图学学报,2013,4(1):46-49 [6] 李松,郝忠孝.基于Voronoi图的反向最近邻查询方法研究[J].哈尔滨工程大学学报,2008,9(3):261-265 [7] 杨泽雪,郝忠孝.基于Voronoi图的线段最近对查询[J].计算机科学,2012,9(6):143-146 [8] Kekeng X,David T.Voronoi-based range and continuous range query processing in mobile databases[J].Journal of Computer and SystemSciences,2011,7(4):637-651 [9] Nutanong S,Tanin E,Zhang Rui.Incremental evaluation of visible nearest neighbor queries[J].IEEE Transactions on Know-ledge Engineering,2010,2:665-681 [10] Gao Yun-jun,Zheng Bai-hua,Chen Gen-cai,et al.Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases[J].IEEE Trans.Knowl.Data Eng.,2009,1:1314-1327 [11] Hu Ling,Jing Yi-nan,Ku Wei-Shinn,et al.Enforcing k Nearest Neighbor Query Integrity on Road Networks[C]∥ACM SIGSPATIAL GIS’12.2012:346-349 [12] Elmongui H G,Mokbel M F,Aref W G.Continuous aggregate nearest neighbor queries[J].GeoInformatica,2013,7(1):63-95 [13] 李艳红,李国徽,杜小坤.路网中双色数据集上连续反向k近邻查询处理的研究[J].计算机科学,2012,9(11):131-136 [14] 苗东菁,石胜飞,李建中.一种局部相关不确定数据库快照集合上的概率频繁最近邻算法[J].计算机研究与发展,2011,8(10):1812-1822 [15] 袁培森,沙朝锋,王晓玲,等.一种基于学习的高维数据c-近似最近邻查询算法[J].软件学报,2012,3(8):2018-2031 [16] Zhang Li-ping,Li Song,Li Lin,et al.Simple Continues Near Neighbor Chain Query of the Datasets Based on the R Tree[J].Journal of Computaional Information Systems,2012,8(22):9159-916 [17] 张丽平,李林,李松,等.预定数据链规模的单纯型连续近邻链查询[J].计算机工程,2012,8(10):51-53 [18] 张丽平,李松,郝忠孝.球面上的最近邻查询方法研究[J].计算机工程与应用,2011,7(5):126-129 [19] 张丽平,李松,郝晓红,等.Jrv 粗糙Vague区域关系[J].浙江大学学报,2012,6(1):122-128 |
No related articles found! |
|