CubiST++

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

CubiST⁺⁺: Evaluating Ad-Hoc CUBE Queries Using Statistics Trees

Full text

Publisher Site

Source

Distributed and Parallel Databases archive
Volume 14 , Issue 3 (November 2003) table of contents

Pages: 221 - 254

Year of Publication: 2003

ISSN:0926-8782

Authors

Joachim Hammer	Computer & Information Science & Eng., University of Florida, Gainesville, FL 32611-6120, USA. jhammer@cise.ufl.edu
Lixin Fu	Division of Computer Science, University of North Carolina, Greensboro, Greensboro, NC 27402-6170, USA. lfu@uncg.edu

Publisher

Kluwer Academic Publishers Hingham, MA, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1023/A:1025537315785

ABSTRACT

We report on a new, efficient encoding for the data cube, which results in a drastic speed-up of OLAP queries that aggregate along any combination of dimensions over numerical and categorical attributes. We are focusing on a class of queries called cube queries, which return aggregated values rather than sets of tuples. Our approach, termed CubiST⁺⁺ (Cubing with Statistics Trees Plus Families), represents a drastic departure from existing relational (ROLAP) and multi-dimensional (MOLAP) approaches in that it does not use the view lattice to compute and materialize new views from existing views in some heuristic fashion. Instead, CubiST⁺⁺ encodes all possible aggregate views in the leaves of a new data structure called statistics tree (ST) during a one-time scan of the detailed data. In order to optimize the queries involving constraints on hierarchy levels of the underlying dimensions, we select and materialize a family of candidate trees, which represent superviews over the different hierarchical levels of the dimensions. Given a query, our query evaluation algorithm selects the smallest tree in the family, which can provide the answer. Extensive evaluations of our prototype implementation have demonstrated its superior run-time performance and scalability when compared with existing MOLAP and ROLAP systems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
	2	Rakesh Agrawal , Ashish Gupta , Sunita Sarawagi, Modeling Multidimensional Databases, Proceedings of the Thirteenth International Conference on Data Engineering, p.232-243, April 07-11, 1997
	3	3. Arbor Systems, "Large-scale data warehousing using hyperion essbase OLAP technology," Arbor Systems, White Paper 1997.
	4	Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	5	Surajit Chaudhuri , Umeshwar Dayal, Data warehousing and OLAP for decision support, ACM SIGMOD Record, v.26 n.2, p.507-508, June 1997
	6	Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
	7	Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
	8	8. E.F. Codd, S.B. Codd, and C.T. Salley, "Beyond decision support," in Computer World, vol. 27, 1993, www.arborsoft.com/OLAP.html.
	9	9. E.F. Codd, S.B. Codd, and C.T. Salley, "Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate," Technical Report 1993.
	10	Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
	11	Curtis E. Dyreson, Information Retrieval from an Incomplete Data Cube, Proceedings of the 22th International Conference on Very Large Data Bases, p.532-543, September 03-06, 1996
	12	Lixin Fu , Joachim Hammer, CubiST: a new algorithm for improving the performance of ad-hoc OLAP queries, Proceedings of the 3rd ACM international workshop on Data warehousing and OLAP, p.72-79, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/355068.355318]
	13	Sanjay Goil , Alok Choudhary, High Performance OLAP and Data Mining on Parallel Computers, Data Mining and Knowledge Discovery, v.1 n.4, p.391-417, December 1997 [doi>10.1023/A:1009777418785]
	14	Sanjay Goil , Alok Choudhary, PARSIMONY: An infrastructure for parallel multidimensional analysis and data mining, Journal of Parallel and Distributed Computing, v.61 n.3, p.285-321, March 1, 2001 [doi>10.1006/jpdc.2000.1691]
	15	Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
	16	16. H. Gupta and I. Mumick, "Selection of views to materialize under a maintenance cost constraint," Stanford University, Technical Report, 1997.
	17	Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, ACM SIGMOD Record, v.25 n.2, p.205-216, June 1996
	18	18. Information Advantage, "Business intelligence," White Paper, 1998.
	19	19. Informix Corp., "Informix red brick decision server," 2001, http://www.informix.com/redbrick/.
	20	20. T. Johnson and D. Shasha, "Some approaches to index design for cube forests," Bulletin of the Technical Committee on Data Engineering, IEEE Computer Society, vol. 20, pp. 27-35, 1997.
	21	Wilburt Labio , Dallan Quass , Brad Adelberg, Physical Database Design for Data Warehouses, Proceedings of the Thirteenth International Conference on Data Engineering, p.277-288, April 07-11, 1997
	22	22. M. Lee and J. Hammer, "Speeding up warehouse physical design using a randomized algorithm," International Journal of Cooperative information Systems (IJCIS)--Special Issue on Design and Management of Data Warehouses, vol. 10, pp. 327-354, 2001.
	23	23. D. Lomet, "Bulletin of the technical committee on data engineering," in Special Issue on Materialized Views and Data Warehousing, J. Widom (Ed.), IEEE Computer Society, 1995, vol. 18.
	24	24. Microsoft Corp., "Microsoft SQL server," Microsoft, Seattle, WA, White Paper.
	25	25. MicroStrategy Inc., "The case for relational OLAP," MicroStrategy, White Paper.
	26	Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, ACM SIGMOD Record, v.26 n.2, p.38-49, June 1997
	27	Patrick E. O'Neil, Model 204 Architecture and Performance, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.40-59, September 28-30, 1987
	28	28. Oracle Corp., "Oracle express OLAP technology," http://www.oracle.com/olap/index.html.
	29	29. Oracle Corp., "Oracle express server documentation," Oracle Corporation, Redwood Shores, CA, Documentation, August 2001.
	30	30. Pilot Software Inc., "An introduction to OLAP multidimensional terminology and technology," Pilot Software, Cambridge, MA, White Paper.
	31	31. Redbrick Systems, "Decision-makers, business data and RISQL," Informix, Los Gatos, CA, White Paper, 1997.
	32	Nick Roussopoulos , Yannis Kotidis , Mema Roussopoulos, Cubetree: organization of and bulk incremental updates on the data cube, ACM SIGMOD Record, v.26 n.2, p.89-99, June 1997
	33	Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
	34	Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
	35	J. Srivastava , J. S. E. Tan , V. Y. Lum, TBSAM: An Access Method for Efficient Processing of Statistical Queries, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.414-423, December 1989 [doi>10.1109/69.43417]
	36	36. Transaction Processing Performance Council, "The TPC Benchmark<sup>TM</sup>H," Transaction Processing Council, 2001, http://www.tpc.org/tpch/.
	37	37. Transaction Processing Performance Council. "Transaction processing performance council," 2001, http://www.tpc.org/.
	38	Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995
	39	Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton, An array-based algorithm for simultaneous multidimensional aggregates, ACM SIGMOD Record, v.26 n.2, p.159-170, June 1997
	40	Yue Zhuge , Hector Garcia-Molina , Janet L. Wiener, Consistency Algorithms for Multi-Source Warehouse View Maintenance, Distributed and Parallel Databases, v.6 n.1, p.7-40, Jan., 1998 [doi>10.1023/A:1008698814840]