A Pareto Model for OLAP View Size Estimation

On-Line Analytical Processing (OLAP) aims at gaining useful information quickly from large amounts of data residing in a data warehouse. To improve the quickness of response to queries, pre-aggregation is a useful strategy. However, it is usu-ally impossible to pre-aggregate along all combinations of the dimensions. The multi-dimensional aspects of the data lead to combinatorial explosion in the number and potential storage size of the aggregates. We must selectively pre-aggregate. Cost/benefit analysis involves estimating the storage requirements of the ag-gregates in question. We present an original algorithm for esti-mating the number of rows in an aggregate based on the Pareto distribution model. We test the Pareto Model Algorithm empiri-cally against four published algorithms, and conclude the Pareto Model Algorithm is consistently the best of these algorithms for estimating view size