How to evaluate multiple range-sum queries progressively

ABSTRACT

Users of decision support system typically submit batches of range-sum queries simultaneously rather than issuing individual, unrelated queries. We propose a wavelet based technique that exploits T/O sharing across a query batch to evaluate the set of queries progressively and efficiently. The challenge is that now controlling the structure of errors across query results becomes more critical than minimizing error per individual query. Consequently, we define a class of structural error penalty functions and show how they are controlled by our technique Experiments demonstrate that our technique is efficient as an exact algorithm, and the progressive estimates are accurate, even after less than one I/O per query.

REFERENCES

• 1: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 2: Chee Yong Chan , Yannis E. Ioannidis, Hierarchical Prefix Cubes for Range-Sum Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.675-686, September 07-10, 1999
• 3: Steven Geffner , Divyakant Agrawal , Amr El Abbadi, The Dynamic Data Cube, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.237-253, March 27-31, 2000
• 4: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Marin J. Strauss, Optimal and approximate computation of summary statistics for range aggregates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375598]
• 5: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 6: Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.463-474, May 15-18, 2000, Dallas, Texas, United States
• 7: 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
• 8: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 9: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 10: Viswanath Poosala , Venkatesh Ganti, Fast Approximate Answers to Aggregate Queries on a Data Cube, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.24-33, July 28-30, 1999 [doi>10.1109/SSDM.1999.787618]
• 11: Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, pCube: Update-Efficient Online Aggregation with Progressive Feedback and Error Bounds, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.95, July 26-28, 2000 [doi>10.1109/SSDM.2000.869781]
• 12: Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Flexible Data Cubes for Online Aggregation, Proceedings of the 8th International Conference on Database Theory, p.159-173, January 04-06, 2001
• 13: R. R. Schmidt and C. Shahabi. Wavelet based density estimators for modeling OLAP data sets. In SIAM Workshop on Mining Scientific Datasets, Chicago, April 2001. Available at http://infolab.usc.edu/publication.html.
• 14: Rolfe R. Schmidt , Cyrus Shahabi, ProPolyne: A Fast Wavelet-Based Algorithm for Progressive Evaluation of Polynomial Range-Sum Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.664-681, March 25-27, 2002
• 15: Jayavel Shanmugasundaram , Usama Fayyad , P. S. Bradley, Compressed data cubes for OLAP aggregate query approximation on continuous dimensions, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.223-232, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312231]
• 16: Shin-Chung Shao, Multivariate and Multidimensional OLAP, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.120-134, March 23-27, 1998
• 17: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 18: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, Using wavelet decomposition to support progressive and approximate range-sum queries over data cubes, Proceedings of the ninth international conference on Information and knowledge management, p.414-421, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354848]
• 19: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.271-282, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

General Terms:
Design, Languages, Performance