CubiST: A New Algorithm for Improving the Performance of Ad-hoc OLAP Queries

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Lixin Fu, Associate Professor (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: Being able to efficiently answer arbitrary OLAP queries that aggregate along any combination of dimensions over numerical and categorical attributes has been a continued, major concern in data warehousing. In this paper, we introduce a new data structure, called Statistics Tree (ST), together with an efficient algorithm called CubiST, for evaluating ad-hoc OLAP queries on top of a relational data warehouse. We are focusing on a class of queries called cube queries, which generalize the data cube operator. CubiST represents a drastic departure from existing relational (ROLAP) and multi-dimensional (MOLAP) approaches in that it does not use the familiar view lattice to compute and materialize new views from existing views in some heuristic fashion. CubiST is the first OLAP algorithm that needs only one scan over the detailed data set and can efficiently answer any cube query without additional I/O when the ST fits into memory. We have implemented CubiST and our experiments have demonstrated significant improvements in performance and scalability over existing ROLAP/MOLAP approaches.

Additional Information

Publication
ACM Third International Workshop on Data Warehousing and OLAP (DOLAP?00), Washington, D.C, USA, November, 2000, pages 72-79
Language: English
Date: 2000
Keywords
Data cube, Data warehouse, Index structure, OLAP, Query processing, Query optimization, Algorithms, Performance, Design, Experimentation, Languages, Theory