Structural Index For PrefixCube

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.