障碍物环境下的动态单纯型连续近邻链查询-论文.pdf

《障碍物环境下的动态单纯型连续近邻链查询-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第8期计算机工程2014年8月Vo1．40No．8ComputerEngineeringAugust2014·先进计算与数据处理·文章编号：1000．3428(2014)08．0052~6文献标识码：A中图分类号：TP311障碍物环境下的动态单纯型连续近邻链查询李松，张丽平，刘艳，郝晓红，杨和禹(哈尔滨理T大学a．计算机科学与技术学院；b．计算中心，哈尔滨150080)摘要：单纯型连续近邻链查询在空间数据查询、空间数据挖掘和网络搜索等领域具有重要意义。针对障碍物环境下动态数据集中的单纯型连续近邻链查询问题，着重考虑新增

2、点和删除点对初始单纯型连续近邻链的影响，基于判定圆域对初始单纯型连续近邻链进行二次计算和判断，提出在数据集动态增大和动态减小环境下的OB—DYNSCNNC—ADD和OB—DYNSCNNC—DET查询算法，以实现对数据集的有效筛选和过滤。理论研究和实验分析表明，2种算法均能实现障碍物环境下动态数据集中的单纯型连续近邻链查询，并具有较高的查询效率。关键词：空间数据库；空间索弓i结构；最近邻查询；连续近邻链；障碍线；判定圆域DynamicSimpleContinuesNearNeighborChainQuerywithObstacl

3、esLISong，ZHANGLi—ping，LIUYan，HAOXiao—hong，YANGHe—yu(a．SchoolofComputerScienceandTechnology；b．ComputingCenter，HarbinUniversityofScienceandTechnology，Harbin150080，China)【Abstract】TheSimpleContinuesNearNeighborChain(SCNNC)queryhasimportantsignificanceinthespatialdataqu

4、ery，spatialdatamining，Websearch，etc．AccordingtotheproblemthattheexistingquerymethodscannothandletheSCNNCqueryindynamicdatasetwithobstacles，theinfluenceofthepointsinsertionanddeletiontotheSCNNCareeonsidered．TheOBDYNSCNNCADDalgorithmandtheOBDYNSCNNCDETalgorithmaregive

5、nforthedataset————————increasingdynamicallyandthedatasetdecreasingdynamicallybasedonthejudgingcircleandthefilteringmethods．Theperformanceofthemethodsareanalyzedandcomparedbyexperiment．Thetheatricalstudyandtheexperimentalresultsshowthatthealgorithmshavegreatadvantage

6、sfortheSCNNCqueryindynamicdatasetwithobstacles．【Keywords】spatialdatabase；spatialindexstructure；nearestneighborquery；ContinuesNearNeighborChain(CNNC)；obstacleline；judgingcircleDoI：10．3969／j．issn．1000—3428．2014．08．011询、高维数据近似最近邻查询、不确定数据集的1概述概率频繁最近邻查询、基于Voronoi图的反向最数据集

7、中的近邻查询问题在空间数据库、海量近邻查询等方面。所取得的成果解决了最近邻数据查询与分析、大数据处理、数据挖掘、图像处理查询领域的一系列重要问题。和交通控制等领域具有重要的研究意义。国内外学作为最近邻查询领域的一个变种问题，单纯型者对近邻查询问题进行了广泛研究，在简单最近邻、连续近邻链(SimpleContinuesNearNeighborChain，反向最近邻、组最近邻、线段最近邻和最近对查询等SCNNC)查询在空间数据挖掘、数据相似性分析和方面取得了一些重要研究成果。智能推理等领域具有较大的作用。已有的研究成近年来，由于数

8、据量的显著增长和实际应用的果无法有效地查询单纯型连续近邻链，为处理需要，数据集中的近邻查询及其变种问题成为研究单纯型连续近邻链问题，文献[12]基于计算几何巾的热点。国内外的研究进一步拓展到移动查询点的的Voronoi图对数据集中单纯型连续近邻链问题进最近邻查询、道路网中的连