CKDB-Tree：一种有效的高维动态索引结构

《CKDB-Tree：一种有效的高维动态索引结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngdneeringandApplications计算机工程与应用2009，45(30)157CKDB—Tree：一种有效的高维动态索引结构孙劲光，王淑娥SUNJin—guang，WANGShu—e辽宁工程技术大学电子与信息]：程学院，辽宁葫芦岛125105SchoolofElectronicandInformation，LiaoningTechnicalUniversity，Huludao，Liaoning125105，ChinaE-mail：3337276wanghan@163．comSUNJin-guang，WANGShu-e．CKD

2、B—Tree：Efectiveindexstructureinhigh-dimensionaldataspaces．ComputerEngineeringandApplications．2009．45(30)：157-160．Abstract：AneffectiveindexStPdCtUl’eisproposedforhigh—dimensionaldataspaces：CKDB—Tree(CompactKDB—Tree)．Theindexstructureusesonekindofnewpartitioningstrategy．Duringtheinse

3、~processing。thispaperintroducesthesafe—inserted—nodeandsafe—deletednodeconceptintothestructure，whichisnoton1)consideringthecurrentnode，butalsoconsideringthefuturenode．ThispapergivesthedefinitionoftheCKDB—Treeandthecharacterofthenode；italsogivesthealgorithmoftheinsert，thesearchandth

4、edeleteoperation；thengivestheanalysisandtheinferencetotheindexstructure’smemoryprope~y；finally，theexperimentprovesthatCKDB-TreeisonekindofeffectiveLl、namicindexstructureinthehigh—dimensionalspaces．Keywords：high—dimensionaldataspace；CompactKDB～Tree；splittingpolicy；dynamicindexstruct

5、ure摘要：在高维数据空间中提出了一种新的索引结构：CKDB—Tree(CompactKDB—Tree)，该索引结构采用一种新的分裂策略，在进行分裂时，引入插入安全点和删除安全点的概念，不仅考虑到将来的数据，而且对已经进行索引的数据也进行考虑；给出了CK—DB—Tree的定义以及节点结构的特点，针对CKDB—Tree，给出了相应的插入、查找、删除操作的算法；对该索引结构的存储性能进行定量分析和推理；最后经实验证明，CKDB—Tree是高维空间中一种有效的动态索引结构。欠键词：高维数据空间；压缩KDB树；分裂策略；动态索引结构DOI-10．3778／j．iss

6、n．1002—8331．2009．30，048文章编号：1002—8331(2009)30—0157—04文献标识码：A巾图分类号：TP3l1传统的高维数据索引结构在维度较高的情7兑下，其检索性间进行无重叠划分，根节点就是整个数据区域，同层的节点各能和内存利用率迅速下降，这就是所谓的“维度灾难”⋯。现有的自所包含的区域之间没有重叠。若一个区域节点的子节点仍然空间划分策略主要有静态划分策略(PyrmnidTeehniquC、Gain—是区域节点，则此节点所代表的空问区域为它的所有子区域节maI1、ThetaI31)和动态划分策略(KDB—Tree[41)及其变

7、种、R—Tree点的区域之和；若子节点为叶子节点，则叶子节点中所有的数及其变种)。由于空间划分的不恰当，从而造成索引结构的不合据点都在此区域内。理，使其索引结构的性能下降。一直被认为理想的高维数据索引定义1CKDB—Tree具有以下特征：结构的金字塔技术在高维稀疏空间会引发不唯一的金字塔值、(1)若根不是叶子节点，则它至少有两棵子树；假命中目、损失的空问邻接性等问题，而可以有效适应动态数据(2)树的每个节点最多有棵子树；除根之外的内部节点分布的KDB-Tree，在维度较高时由于采用不合理的分裂策略，至少有m棵子树；导致索引结构的增大，降低了内存的利用率和检索

8、的性能嘲。(3)所有的叶子节点出现在树的同一层次上并