PrefixCube: Prefix-sharing Condensed Data Cube

Abstract

BST Condensed Cube is a fully computed cube that condenses those tuples, which are aggregated from the same single base relation tuple, into one physical tuple. Although it has been proved to be an effective approach to reduce the size of a data cube, there still exist some redundancies in a BST condensed cube, i.e., prefix redundancy among cube tuples. In this paper, we augument BST condensing with prefix-sharing, and propose an efficient cube structure called PrefixCube, for further reducing a BST condensed data cube's size as well as its computation time. The space and time savings of PrefixCube, compared with its corresponding BST condensed cube, are demonstrated through extensive experiments, using both synthetic and real world data.