The Iterative Data Cube

Data cubes provide aggregate information to support the analysis of thecontents of data warehouses and databases. An important tool to analyze datain data cubes is the range query. For range queries that summarize largeregions of massive data cubes, computing the query result on-the-fly can resultin non-interactive response times (e.g. in the order of minutes). To speed uprange queries, values that summarize regions of the data cube are pre-computedand stored. This faster response time results in more expensive updates and/orspace overhead. In this paper a technique is presented that generates a newclass of schemes that support range queries on data cubes -- Iterative DataCubes. The main idea is that techniques that provide a certain tradeoff ofquery and update costs for a one-dimensional data cube are applied iterativelyalong the dimensions of data cubes of higher dimensionality. The differentone-dimensional techniques can be combined, resulting in a great variety ofIterative Data Cubes. We show that Iterative Data Cubes are easy to generate,analyze and implement. They generalize previous seemingly unrelatedapproaches. Our technique is applicable to aggregate operators and attributesif the attribute\'s domain forms an abelian group under the aggregate operator(e.g., integers under addition). In this paper we focus on techniques that donot cause any space overhead for dense data cubes.