Xiang Rui Chen , Yan Li , Dong Wook Lee , Gyoung Bae Kim , Hae Young Bae

The KIPS Transactions:PartD, Vol. 16, No. 4, pp. 475-486, Aug. 2009
10.3745/KIPSTD.2009.16.4.475,   PDF Download:

Abstract

Data cube plays an important role in multi-dimensional, multi-level data analysis. Meeting on-line analysis requirements of data stream, several cube structures have been proposed for OLAP on data stream, such as stream cube, flowcube, S-cube. Since it is costly to construct data cube and execute ad-hoc OLAP queries, more research works should be done considering efficient data structure, query method and algorithms. Stream cube uses H-cubing to compute selected cuboids and store the computed cells in an H-tree, which form the cuboids along popular-path. However, the H-tree layoutis disorderly and H-cubing method relies too much on popular path.In this paper, first, we propose H*-tree, an improved data structure, which makes the retrieval operation in tree structure more efficient. Second, we propose an improved cubing method, H*-cubing, with respect to computing the cuboids that cannot be retrieved along popular-path when an ad-hoc OLAP query is executed. H*-tree construction and H*-cubing algorithms are given. Performance study turns out that during the construction step, H*-tree outperforms H-tree with a more desirable trade-off between time and memory usage, and H*-cubing is better adapted to ad-hoc OLAP querieswith respect to the factors such as time and memory space.

Statistics
Cite this article