Improving estimation accuracy of aggregate queries on data cubes

ABSTRACT

In this paper, we investigate the problem of estimation of a target database from summary databases derived from a base data cube. We show that such estimates can be derived by choosing a primary database which uses a proxy database to estimate the results. This technique is common in statistics, but an important issue we are addressing is the accuracy of these estimates. Specifically, given multiple primary and multiple proxy databases, that share the same summary measure, the problem is how to select the primary and proxy databases that will generate the most accurate target database estimation possible. We propose an algorithmic approach for determining the steps to select or compute the source databases from multiple summary databases, which makes use of the principles of information entropy. We show that the source databases with the largest number of cells in common provide the more accurate estimates. We prove that this is consistent with maximizing the entropy. We provide some experimental results on the accuracy of the target database estimation in order to verify our results.

REFERENCES

• 1: Deming, W. E. & Stephan, F. F. (1940). On a least square adjustment of a sampled frequency table when the expected marginal totals are known, Annals of Mathematical Statistics 11: 427--444.
• 2: Ghosh, M. & Rao, J. N. K. (1994). Small area estimation: An appraisal, Statistical Science 9: 55--93.
• 3: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 4: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 5: Jaynes, E. (1979). Where do we stand on maximum entropy?, The Maximum Entropy Formalism, R. Levine and M. Tribes Eds., MIT Press, Cambridge, MA, pp. 15--118.
• 6: Kullback, S. (1959). Information Theory and Statistics, J. Wiley & Sons, Inc., London.
• 7: Customized Answers to Summary Queries via Aggregate Views, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.193, June 21-23, 2004 [doi>10.1109/SSDBM.2004.26]
• 8: Francesco M. Malvestuto , Elaheh Pourabbas, Local computation of answers to table queries on summary databases, Proceedings of the 17th international conference on Scientific and statistical database management, p.263-270, June 27-29, 2005, Santa Barbara, CA
• 9: Francesco M. Malvestuto, A universal-scheme approach to statistical databases containing homogeneous summary tables, ACM Transactions on Database Systems (TODS), v.18 n.4, p.678-708, Dec. 1993 [doi>10.1145/169725.169712]
• 10: Themis Palpanas , Nick Koudas , Alberto Mendelzon, Using Datacube Aggregates for Approximate Querying and Deviation Detection, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1465-1477, November 2005 [doi>10.1109/TKDE.2005.187]
• 11: Elaheh Pourabbas , Arie Shoshani, Efficient estimation of joint queries from multiple OLAP databases, ACM Transactions on Database Systems (TODS), v.32 n.1, p.2-es, March 2007 [doi>10.1145/1206049.1206051]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Experimentation, Management, Theory

Keywords:
accuracy analysis, entropy, query estimation