Using Wavelet Decomposition to Support Progressive and ApproximateRange-Sum Queries over Data Cubes

Data cubes are designed to provide aggregate information that can be used toanalyze the contents of databases and data warehouses. A range query appliesan aggregation operation (e.g., SUM, AVERAGE) over all selected cells in a datacube, where the selection is specified by providing ranges of values ondifferent dimensions. Previous approaches to process the range sum query ondata cubes (e.g., prefix sum) have low query costs but have high update costs.We use the discrete wavelet transformation to decompose a data cube intowavelet coefficients of different resolutions. The resulting decomposed datacube can be used for progressive and approximate query processing. This newapproach can handle clustered and sparse data gracefully and can provideefficient performance for both queries and updates, which makes the waveletdecomposition technique suitable for dynamic data cube environments.