【作者】 聂晶；

【导师】 冯剑琳；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2006， 硕士

【摘要】 前缀立方是最近提出的一种数据立方结构,它利用前缀共享和基本单元技术,在浓缩数据立方的基础上进一步消除了数据小方内的前缀冗余,从而进一步减小了数据立方的尺寸。由于对数据立方的任一范围查询事实上均可最终归结为针对其中特定数据小方的范围查询,所以前缀立方仍然按数据小方聚簇,在每一个数据小方内,立方元组按照共享维值进行聚簇,并且通过共享前缀形成分组结构。由于分组结构的存在,前缀立方不能沿用浓缩数据立方的索引,必须为它寻求一种新的索引机制。研究工作者最近提出了前缀立方的一种索引机制Prefix-CuboidTree。它结合C-曲线和B-Tree索引结构成功地对前缀立方进行索引。该索引范围查询算法采用深度优先的策略,通过查询点跳跃减少了I/O代价。现实世界中的数据往往都是非均匀分布的,所以在整个数据空间中大部分空间是未为利用的死区。怎样避免对死区的查询成为提升索引的查询性能至关重要的问题之一。而Prefix-CuboidTree并没有考虑到这个问题,因此,基于BUB-Tree和R-Tree索引技术得到了前缀立方的一种新的索引机制Bound-CuboidTree。它在每个数据小方内以Z-顺序保持分组的空间临近性,然后使用BUB-Tree对每个数据小方进行索引,减少了范围查询时的死区,提高了查询效率。同时参考R-Tree生长机制,通过选取插入后索引节点表示范围的增量最少的那个索引节点进行插入,成功解决了BUB-Tree不能在索引节点的Z-曲线编码范围是连续且不相交的情况下使用的问题。在此基础上提出了这种索引的广度优先策略的范围查询算法,避免了因为Prefix-CuboidTree因为误中而产生的I/O代价。实验结果表明:Bound-CuboidTree在大多数情况下要比Prefix-CuboidTree性能更好,更适合前缀立方的结构。更多还原

【Abstract】 Recently a new data cube structure called PrefixCube was proposed, which reduces the size of normal data cube efficiently by augmenting BST condensing with prefix-sharing. Whenever a query against some data cube figured by ODM is issued, it’s natural to decompose it into several sub-queries respectively against some particular cuboid, and hence all PrefixCube tuples belonging to the same cuboid are clustered. the Tuples with same prefix form group structures by prefix-sharing.It is nessecery to seek a new index mechanism for prefix-cube instead of following the index mechanism of condensed cube for the group structure. Prefix-CuboidTree was proposed for prefixcube indexing formerly which actually is B-Tree collection by projecting data cube into linear space in C-Curve. It reduces I/O operations by jumping in depth-first search when range querying.Real world data has usually a non-uniform data distribution, but most of the universe is unpopulated space, the so called dead space. When indexing such data it is important to handle also dead space efficiently. Unforyunately Prefix-CuboidTree didn’t consider the dead space. So based on BUB-Tree and R-Tree, the Bound-CuboidTree was proposed for prefixcube indexing. It uses Z-Curve instead of C-Curve to project the data cube space for spatial imformation keeping and the BUB-Tree instead of B-Tree for dead space handling. Besides it resolves the problrm that the BUB-tree can’t be used in Z-Bound intersecting situation by introducing the R-Tree growing algorithm. The range query on Bound-CuboidTree with width-first strategy, and so reduces the I/O caused by the false hit in Prefix-CuboidTree.According to the results of extensive experiments, Bound-CuboidTree is more efficient for PrefixCube than Prefix-CuboidTree.更多还原