基于混合聚类算法的动态r树一

《基于混合聚类算法的动态r树一》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第37卷第2期中南大学学报(自然科学版)Vo1．37NO．22006年4月J．CENT．SOUTHUNIV．(SCIENCEANDTECHNOLOGY)Apr．2006基于混合聚类算法的动态R一树黄继先，鲍光淑，夏斌(1．中南大学地学与环境工程学院，湖南长沙，410083；2．中国科学院广州地球化学研究所，广东广州，510640；3。中南大学信息物理工程学院，湖南长沙，410083)摘要：针对动态树是通过动态插入算法建立起来的，其节点分裂算法的性能直接影响到R_树的性能和查询效率的问题，为了使动态R_树适应多雏复杂空间数据的要求，提出一种用于实现R一树节点分裂的混合聚类算法(

2、HCR)，它建立在普通聚类算法的基础上，并进行了一系列扩充。针对空间对象的均匀分布与不均匀分布，HCR算法在实现R_树节点分裂时分别采用不同的聚类准则以提高其聚类效果和查询效率。此外，还将HCR算法与其他算法进行对比实验，结果表明该算法具有较高的查询效率。关键词：空间索引；R一树；混合聚类算法}CR一树中图分类号：P208文献标识码：A文章编号：1672-7207(2006)02—0366—05AdynamicR-treeindexbasedonhybridclusteringalgorithmHUANGJi—xianl-，BAOGuang-shu。，XIABin(1．Sch

3、oolofGeoscienceandEnvironmentalEngineering。CentralSouthUniversity，Changsha410083，China；2．GuangzhouInstituteofGeochemistry，ChineseAcademyofSciences，Guangzhou510640，China；3．SchoolofInfo-physicsandGeomaticsEngineering，CentralSouthUniversity，Changsha410083，China)Abstract：ConsideringthatdynamicR

4、—treeisimplementedbydynamicinsertionalgorithm，anditsqualityofsplittingalgorithminfluencesdirectlytheperformanceofR—-treeandqueryingefficien。-cy，inordertomeetthedemandsofmulti—dimensionandcomplexspatialdata，thehybridcluste—ring(HCR)algorithmwasproposedforthenodessplittingofR—treewhichwasbase

5、donthecommonclusteringalgorithms，andsomeextensionswerebuilt．Accordingtothedifferenceofspatialobjectsdistributedevenlyandunevenly，differentclusteringruleswereadoptedtoimprovethequeryefficiency．Somecomparisonsandexperimentswereconducted．Theresultsshowthatthehybridclusteringalgorithmhashigheff

6、iciencyinquerying．Keywords：spatialindex；R—tree；hybridclusteringalgorithm；CR～treeR一树是目前应用最广泛的一种数据结构。询效率会大大降低。为此，许多学者对R-树的性能动态R一树一般是通过动态插入算法来建立的，可进行了改进，衍生出许多R-树变种，典型的有R一以保证其空间利用率在5O％以上，但其结构不树[、R一树引、压缩R一树嘲、HilbertRft。等。可避免地会导致约束矩形间相互重叠区域并出现空其中，R树是最有效的R一树变种之一，它能对覆白空间。随着其重叠区域和空白区域的增大，其查盖区域、重叠面积和

7、边界周长进行启发式优化，并收稿B期：2005一O6一l3基金项目：湖南省自然科学基金资助项目(04JJ30O46)作者简介：黄继先(1973一)。女，湖南临澧人，博士，讲师。从事GIS空间数据库、GIS系统开发等研究论文联系人：黄继先，女，博士；电话：13826060796(手机)；E—mail：jxhuang@mail．CSU．edu．cn第2期黄继先，等t基于混合聚类算法的动态R一树·367·通过重新插入节点重建R一树以提高其性能。但重新空间矩形范围的并集，而交叠指叶子结点占据的空插入过程相当繁琐，