受限区域内的单纯型连续近邻链查询方法.pdf

《受限区域内的单纯型连续近邻链查询方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JournalofComputerApplicationsISSN1001—90812014．02．10计算机应用，2014，34(2)：406—410C0DENJYIIDUhttp：／／www．joca．cn文章编号：1001—9081(2014)02．0406．05doi：10．11772／j．issn．1001—9081．2014．02．0406受限区域内的单纯型连续近邻链查询方法张丽平，李松，赵纪桥，郝晓红(1．哈尔滨理工大学计算机科学与技术学院，哈尔滨150080；2．哈尔滨理工大学计算中心，哈尔滨150080)(通信作者电子邮箱lisongb

2、eifen@163．com)摘要：由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题，针对受限区域和障碍物的复杂性，详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法，分别提出了VORNB——CRSCNNC算法和V0R—CB—CRSCNNC算法。算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算，每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点，预先过滤掉大量数据，减少每次计算涉及的数据量。理论研究和实验分析表明，所提出的算法在查询过程中减少了数据逐一判断的冗余计

3、算，受受限区域形状的影响较小，较大程度提高了查询效率。关键词：空间数据库；Voronoi图；最近邻查询；单纯型连续近邻链；受限区域中图分类号：TP311．13文献标志码：ASimplecontinuousnearneighborchainqueryinconstrainedregionsZHANGLiping，LISong，ZHAOJiqiao，HAOXiaohong(1．SchoolofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,HarbinHeilongjia

4、ng150080，China；2．ComputationCenter,HarbinUniversityofScienceandTechnology,HarbinHeilongjiang150080，China)Abstract：Theexitingmethodsofthenearestneighborquerycannotsearchthesimplecontinuousnearneighborchainintheconstrainedregions．Toremedythedeficiencyoftheexistingwork，accordingtoth

5、ecomplexityoftheconstrainedregionsandtheobstacles，thesimplecontinuousnearneighborchainquerywithnonobstaclesandwithobstacleswerestudiedrespectively．TheVORNBCRSCNNCalgorithmandtheVORCBCRSCNNCalgorithmwerepresented．Thespatialdata————————werefiheredandcomputedbasedontheVoronoidiagram

6、andthejudgingcircles．ThecalculationsofeachquerywerereducedbyonlyconsideringthepointswhichlayintheVoronoipolygonandthejudingcircles．Thetheatricalstudyandtheexperimentalresultsshowthattheredundantcalculationisreducedandthequeryeficiencyislessaffectedbytheconstrainedregions．Keywords

7、：spatialdatabase；Voronoidiagram；nearestneighborquery；SimpleContinuesNearNeighborChain(SCNNC)；constrainedregion续近邻链(SimpleContinuesNearNeighborChain，SCNNC)查0引言询在空间数据挖掘、数据相似性分析和空间智能推理等领域空间数据信息的近邻关系查询问题是空间数据查询的一具有较大的作用。已有的研究成果”‘。没有涉及SCNNC查个重要方面。空间数据集的近邻关系查询在空间数据挖掘、询问题，提出的方法不适合处理SCNN

8、C查询与分析。为了处地理信息系统、相似性分析、空间定位和地图检索等领域具有理预定