一种新的前缀立方索引机制

《一种新的前缀立方索引机制》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、http://www.paper.edu.cn*一种新的前缀立方索引机制聂晶冯剑琳王元珍（华中科技大学计算机科学与技术系武汉430074）摘要前缀立方在浓缩数据立方的基础上利用前缀共享和基本单元组技术有效地缩小了数据立方的尺寸。由于前缀共享产生的分组结构，浓缩数据立方的索引CuboidTree并不适合前缀立方。所以，根据前缀立方包含分组结构的特性，结合BUB-Tree和R-Tree技术对CuboidTree进行改造，最终得到了一种新的索引机制Bound-CuboidTree。实验证明，这种索引机制比已有的前缀立方索引Prefix-CuboidTree更

2、适合前缀立方的结构。关键词前缀立方，分组，Bound-CuboidTreeAnewindexmechanismforPrefixCubeNIEJingFENGJian-linWangYuanzhen（DepartmentofComputerScienceHuazhongUniversityofScienceandTechnology,Wuhan430074）AbstractPrefixCubebasedoncondensedcubewasproposedtoreducethesizeofdatacubemoreefficientlybyaugmenti

3、ngBSTcondensingwithprefix-sharing.Becauseofthegroupstructureafterprefix-sharing,theCuboidTreeforCondensedcubeindexingisnotappropriateforPrefixCube.ByintroducingBUB-TreeandR-TreetechniqueintoCuboidTree,anewindexmechanismcalledBound-CuboidTreewasproposed.Accordingtotheresultsofext

4、ensiveexperiments,itismoreefficientforPrefixCubethanPrefix-CuboidTree.KeywordsPrefixCube,Group,Bound-CuboidTree有普通立方元组组成，称为普通子立方；另一个由所1引言[2,6]有基本单元组组成，称为单元组子立方。在普通子数据立方[1]通过预先对基本关系表中的数据在所立方中，所有的普通立方元组按数据小方聚簇，即属有可能的维属性组合之上计算聚集来达到减少实时计于同一数据小方的立方元组属于同一个簇，一个簇被算的目的，从而加快OLAP中查询响应速度。但是

5、，称作是一个普通数据小方(normalcuboid)；在单元组子预先计算却使得数据立方占用存储的空间随着维数的立方中，所有的基本单元组按单值维集聚簇，即具有增加而剧增，而存储巨大的数据立方所带来的大量I/O相同单值维集的基本单元组属于同一个簇，一个簇被操作导致了不菲的查询代价。称作是一个虚数据小方(virtualcuboid)。如果给定一个通过研究发现，立方元组之间存在两种冗余，即基表R如表1所示，我们可以的到其前缀立方的基本前缀冗余和后缀冗余。通过消除冗余，新的立方形式，结构如图1所示。如浓缩数据立方[2](CondensedCube)，Dwarf[

6、3]，Quotient表1基本关系表RCube[4]和QC-Trees[5]等，在不破坏数据立方完整性的ABCMt1811100同时大大缩小了数据立方的尺寸。t218150由于浓缩数据立方的各个小方的元组之间依然t312360存在前缀冗余，所以通过压缩这些前缀冗余就得到了空间代价更小的前缀立方(PrefixCube)[6,7]。本文提出一图1是基表R对应的前缀立方结构。前缀立方的种新的前缀立方索引机制Bound-CuboidTree，并通过头节点N-Roots指向一组N-prefixTree，每一棵在真实气象数据及和人造模拟数据集上进行的大量实N-pr

7、efixTree对应一个普通数据小方；头节点V-Roots验来证明其效率。指向一组V-prefixTree，每一棵V-prefixTree对应一个虚数据小方。除普通数据小方Cuboid(CID=ALL)外，2前缀立方N-prefixTree的高度与其对应普通数据小方的聚集属性个数相同；V-prefixTree的高度则等于其对应的虚数前缀立方拥有两个互不相交的子立方，一个由所据小方单值维集中维个数加上单值维集最后一个维之*本文研究得到国家自然科学基金(编号60303030)和ChineseDoctorSiteresearchgrantNo.2003048

8、7032(中国博士点基金)的资助。聂晶，硕士研究生，主要研究方向是OLAP。冯剑琳，博士，主要