Relative Prefix Sums: An Efficient Approach for Querying DynamicOLAP Data Cubes

Range sum queries on data cubes are a powerful tool for analysis. A range sumquery applies an aggregation operation (e.g., SUM) over all selected cells in adata cube, where the selection is specified by providing ranges of values fornumeric dimensions. Many application domains require that information providedby analysis tools be current or \"near-current.\" Existing techniques for rangesum queries on data cubes, however, can incur update costs on the order of thesize of the data cube. Since the size of a data cube is exponential in thenumber of its dimensions, rebuilding the entire data cube can be very costly.We present an approach that achieves constant time range sum queries whileconstraining update costs. Our method reduces the overall complexity of therange sum problem.