An Effective Algorithm to Extract Dense Sub-cubes from a Large Sparse Cube

摘要

A data cube provides aggregate information to support a class of queries such as a range-sum query. To process those queries efficiently, some auxiliary information, i.e. prefix sums, is pre-computed and maintained. In reality however most of high dimensional data cubes are very sparse, causing a serious space overhead. In this paper, we investigate an algorithm that extracts dense sub-cubes from a large sparse cube based on the density function. Instead of maintaining a large prefix-sum cube, a few dense sub-cubes are maintained to reduce the space overhead and to restrict the update propagation. We present an iterative method that identifies dense intervals in each dimension and constructs sub-cubes based on the intervals found. We show the effectiveness of our method through the analytic comparison and experiment with respect to various data sets and dimensions.