Analysis of pre-computed partition top method for range top-k queries in OLAP data cubes

ABSTRACT

In decision support systems, having knowledge on the top k values is more informative and crucial than the maximum value. Unfortunately, the naive method involves high computational cost and the existing methods for range-max query are inefficient if applied directly. In this paper, we propose a Pre-computed Partition Top method (PPT) to partition the data cube and pre-store a number of top values for improving query performance. The main focus of this study is to find the optimum values for two parameters, i.e., the partition factor (b) and the number of pre-stored values (r), through analytical approach. A cost function based on Poisson distribution is used for the analysis. The analytical results obtained are verified against simulation results. It is shown that the PPT method outperforms other alternative methods significantly when proper b and r are used.

REFERENCES

• 1: 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
• 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: Surajit Chaudhuri , Luis Gravano, Evaluating Top-k Selection Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.397-410, September 07-10, 1999
• 4: Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 5: Dong Wook Kim , Eun Jung Lee , Myoung Ho Kim , Yoon Joon Lee, An efficient processing of range-MIN/MAX queries over data cube, Information Sciences: an International Journal, v.112 n.1-4, p.223-237, Dec. 1998 [doi>10.1016/S0020-0255(98)10035-X]
• 6: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 7: Hua-Gang Li , Tok Wang Ling , Sin Yeung Lee, Range-Max/Min Query in OLAP Data Cube, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.467-476, September 04-08, 2000
• 8: Hua-Gang Li , Tok Wang Ling , Sin Yeung Lee , Zheng Xuan Loh, Range Sum Queries in Dynamic OLAP Data Cubes, Proceedings of the Third International Symposium on Cooperative Database Systems for Advanced Applications, p.74, April 23-24, 2001
• 9: 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
• 10: Weifa Liang , Hui Wang , Maria E. Orlowska, Range queries in dynamic OLAP data cubes, Data & Knowledge Engineering, v.34 n.1, p.21-38, July 2000 [doi>10.1016/S0169-023X(00)00007-0]
• 11: Relative Prefix Sums: An Efficient Approach for Querying Dynamic OLAP Data Cubes, Proceedings of the 15th International Conference on Data Engineering, p.328, March 23-26, 1999
• 12: Sin Yeung Lee , Tok Wang Ling , Hua-Gang Li, Hierarchical Compact Cube for Range-Max Queries, Proceedings of the 26th International Conference on Very Large Data Bases, p.232-241, September 10-14, 2000
• 13: ZhongWei Luo , Tok Wang Ling , Chuan-Heng Ang , Sin Yeung Lee , Bin Cui, Range Top/Bottom k Queries in OLAP Sparse Data Cubes, Proceedings of the 12th International Conference on Database and Expert Systems Applications, p.678-687, September 03-05, 2001
• 14: Zheng Xuan Loh , Tok Wang Ling , Chuan-Heng Ang , Sin Yeung Lee, Adaptive Method for Range Top- k Queries in OLAP Data Cubes, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.648-657, September 02-06, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

General Terms:
Algorithms, Experimentation, Performance

Keywords:
OLAP data cube, analysis, range query, top-k