基于Voronoi图的连续反向最近邻查询-论文.pdf

《基于Voronoi图的连续反向最近邻查询-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第1期计算机工程2014年1月Vol_40No．1ComputerEngineeringJanuary2014·开发研究与工程应用·文章编号：1000—_3428(2014)01—_0272—_03文l畎标识码：A中图分类号：TP311基于Voronoi图的连续反向最近邻查询杨泽雪，郝忠孝L(1．哈尔滨理工大学计算机科学与技术学院，哈尔滨150080；2．黑龙江工程学院计算机科学与技术系，哈尔滨150050；3．哈尔滨工业大学计算机科学与技术学院，哈尔滨150001)摘要：为解决动态环境中移动点的连续反向最近邻查询问题，将连续反向最近邻查

2、询分为单色和双色2种情况进行研究。利用移动点Voronoi图，分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理，对算法正确性和可终止性进行证明，分析算法时问复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况，分析每种情况下候选所在区域的变化，在变化区域内进行Voronoi图的重构，得到对应的解决方法。在多数情况下，该算法只需生成局部移动点的Voronoi图即可找到结果，减小了连续反向最近邻查询的代价。关健词：连续反向最近邻查询；空间数据库；空间查询；Voronoi图；拓扑结构；反向最近邻Continuous

3、ReverseNearestNeighborSearchBased0nVoronoiDiagramYANGZe．xue．HA0Zhong-xiao(1．CollegeofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080，China；2．DepartmentofComputerScienceandTechnology,HeilongjiangInstituteofTechnology,Harbin150050，China；3．Colleg

4、eofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001，China)[Abstract]Inordertosolvecontinuousreversenearestneighborqueryofmovingpointsindynamicenvironment，continuousreversenearestneighborqueryisdividedintomonochromaticandbichromaticstudy．ByusingVoronoidiag

5、ramofmovingpoints，monochromaticcontinuousreversenearestneighborandbichromaticcontinuousreversenearestneighborqueryalgorithmaregiven．Therelevanttheoremandproofofthealgorithm’scorrectnessandterminationaregiven，anditstimecomplexityanalysisispresented．Accordingtowhetherthetopolog

6、yoftheVoronoidiagramofmovingpointschanges，ithastwocategories：changeandnochange．Byanalysisofcandidateregionchangesineachcategory,Voronoidiagramisreconstructedinchangeregion，andcorrespondingsolutionsaregiven．Inmostcases，thequeryresultscanbefoundonlyneedinggenerateVoronoidiagram

7、oflocalmovingpoints．Itcanreducethecostofcontinuousreversenearestneighborqueries．[Keywordslcontinuousreversenearestneighborsearch；spatialdatabase；spatialquery；Voronoidiagram；topologystructure；reversenearestneighborDOh1O．3969／j．issn．1000—3428．2014．01．058续过滤和连续精炼2个步骤，并给出新的连续精炼算法

8、1概述CRange-k。文献[3]给出了IGERN算法来实现CRNN查询，随着移动设备和无线网络的广泛应用，移动对象的动该方法只需要定义