Attribute value reordering for efficient hybrid OLAP

ABSTRACT

The normalization of a data cube is the process of choosing an ordering for the attribute values, and the chosen ordering.Our optimized hybrid OLAP storage mechanism was observed to be 44% more storage efficient than ROLAP and the gains due to normalization alone accounted for 45% of this increase in efficiency.

REFERENCES

• 1: E. J. Candé and D. L. Donoho. Curvelets - a surprisingly effective nonadaptive representation for objects with edges. In Curves and Surfaces, 1999.
• 2: David Wai-Lok Cheung , Bo Zhou , Ben Kao , Kan Hu , Sau Dan Lee, DROLAP - A Dense-Region Based Approach to On-Line Analytical Processing, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.761-770, August 30-September 03, 1999
• 3: David W. Cheung , Bo Zhou , Ben Kao , Hu Kan , Sau Dan Lee, Towards the building of a dense-region-based OLAP system, Data & Knowledge Engineering, v.36 n.1, p.1-27, Jan. 2001 [doi>10.1016/S0169-023X(00)00027-6]
• 4: Frank K. H. A. Dehne , Todd Eavis , Andrew Rau-Chaplin, Coarse Grained Parallel On-Line Analytical Processing (OLAP) for Data Mining, Proceedings of the International Conference on Computational Science-Part II, p.589-598, May 28-30, 2001
• 5: Prasad M. Deshpande , Karthikeyan Ramasamy , Amit Shukla , Jeffrey F. Naughton, Caching multidimensional queries using chunks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.259-270, June 01-04, 1998, Seattle, Washington, United States
• 6: D. L. Donoho, M. Vetterli, I. Daubechies, and R. A. DeVore. Data compression and harmonic analysis. IEEE Transactions on Information Theory, 44, 1998.
• 7: Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: 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
• 10: Sanjay Goil , Alok Choudhary, High-performance on-line analytical processing and data mining on parallel computers, 1999
• 11: C. Hahn, S. Warren, and J. London. Edited synoptic cloud reports from ships and land stations over the globe (1982-1991). http://cdiac.ornl.gov/epubs/ndp/ndp026b/ndp026b.htm, last checked on 6/7/2003, 2001.
• 12: S. Hettich and S.D. Bay. The UCI KDD archive. http://kdd.ics.uci.edu, last checked on 6/7/2003, 2000.
• 13: O. Kaser. Compressing arrays by ordering attribute values. under review, 2002.
• 14: O. Kaser. Compressing MOLAP arrays by attribute-value reordering: An experimental analysis. Technical Report TR-02-001, Dept. of CSAS, U. of New Brunswick, Saint John, Canada, 2002.
• 15: O. Kaser and D. Lemire. Attribute Value Reordering for Efficient Hybrid OLAP. Technical Report NRC-46509, National Research Council of Canada, 2003.
• 16: Daniel Lemire, Wavelet-based relative prefix sum methods for range sum queries in data cubes, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.6, September 30-October 03, 2002, Toronto, Ontario, Canada
• 17: J. Li , J. Srivastava, Efficient Aggregation Algorithms for Compressed Data Warehouses, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.515-529, May 2002 [doi>10.1109/TKDE.2002.1000340]
• 18: A. N. Netravali and F. W. Mounts. Ordering techniques for facsimile coding: A review. Proceedings of the IEEE, 68(7):796--807, 1980.
• 19: Wee Keong Ng , Chinya V. Ravishankar, Block-Oriented Compression Techniques for Large Statistical Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.314-328, March 1997 [doi>10.1109/69.591455]
• 20: E. L. Pennec and S. Mallat. Image representation and compression with bandelets. Technical report, École Polytechnique, 2000.
• 21: Sunita Sarawagi , Michael Stonebraker, Efficient Organization of Large Multidimensional Arrays, Proceedings of the Tenth International Conference on Data Engineering, p.328-336, February 14-18, 1994
• 22: Yannis Sismanis , Antonios Deligiannakis , Nick Roussopoulos , Yannis Kotidis, Dwarf: shrinking the PetaCube, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564745]
• 23: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton, An array-based algorithm for simultaneous multidimensional aggregates, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.159-170, May 11-15, 1997, Tucson, Arizona, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Algorithms, Experimentation, Theory

Keywords:
HOLAP, MOLAP, OLAP, chunking, data cubes, multidimensionay binary arrays, normalization