论文部分内容阅读
前缀立方是最近提出的一种数据立方结构,它利用前缀共享和基本单元技术,在浓缩数据立方的基础上进一步消除了数据小方内的前缀冗余,从而进一步减小了数据立方的尺寸。由于对数据立方的任一范围查询事实上均可最终归结为针对其中特定数据小方的范围查询,所以前缀立方仍然按数据小方聚簇,在每一个数据小方内,立方元组按照共享维值进行聚簇,并且通过共享前缀形成分组结构。由于分组结构的存在,前缀立方不能沿用浓缩数据立方的索引,必须为它寻求一种新的索引机制。研究工作者最近提出了前缀立方的一种索引机制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性能更好,更适合前缀立方的结构。