pCube: Update-Efficient Online Aggregation with ProgressiveFeedback and Error Bounds

Data Cubes are used in large data warehouses as a tool for online aggregationof information. Typically, online aggregation is supported by specifying arange query over a multidimensional data cube. As the number of dimensionsincreases, supporting efficient range queries as well as updates to the datacube becomes difficult. Another problem that arises with increaseddimensionality is the sparseness of the data space. In this paper we develop anew data structure referred to as the pCube (data cube for progressivequerying), to support efficient querying and updating of multidimensional datacubes in large data warehouses. pCube provides intermediate results withabsolute error bounds (to allow trading accuracy for fast response time),efficient updates, scalability with increasing dimensionality, andpre-aggregation to support large range queries. We present both a generalsolution and an implementation of pCube and report the results of experimentalevaluations.