H-IQTS: a semantics-aware histogram for compressing categorical OLAP data

ABSTRACT

This paper introduces a novel data cube compression technique for data cubes whose main idea consists in exploiting the knowledge kept in OLAP hierarchies to drive the compression process. This approach leads to the so-called knowledge-oriented data cube compression paradigm, which is a noticeable alternative to the traditional algorithmic-oriented paradigm that focuses the attention on the issue of compressing the data cube like the latter would be a simple multidimensional array without additional knowledge. This amenity allows us to achieve several benefits, among which a more meaningful exploration of the compressed data cube enriched by semantics-aware metaphors. Our analytical contribution is finally completed by a comprehensive experimental evaluation of our proposed technique on both benchmark and real-life data cubes, also in comparison with well-established histogram-based data cube compression techniques.

REFERENCES

• 1: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: D. Barbarà, W. Du Mouchel, C. Faloutsos, P. J. Haas, J. M. Hellerstein, Y. E. Ioannidis, H. V. Jagadish, T. Johnson, R. T. Ng, V. Poosala, K. A. Ross, and K. C. Sevcik, "The New Jersey Data Reduction Report", IEEE Data Engineering Bulletin, Vol. 20, No. 4, pp. 3--45, 1997.
• 3: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 4: Francesco Buccafurri , Filippo Furfaro , Gianluca Lax , Domenico Saccà, Binary-Tree Histograms with Tree Indices, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.861-870, September 02-06, 2002
• 5: Francesco Buccafurri , Filippo Furfaro , Domenico Sacca , Cristina Sirangelo, A quad-tree based multiresolution approach for two-dimensional summary data, Proceedings of the 15th international conference on Scientific and statistical database management, p.127-140, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214974]
• 6: Alfredo Cuzzocrea, Overcoming Limitations of Approximate Query Answering in OLAP, Proceedings of the 9th International Database Engineering & Application Symposium, p.200-209, July 25-27, 2005 [doi>10.1109/IDEAS.2005.41]
• 7: A. Cuzzocrea, D. Saccà, and P. Serafino, "Semantics-aware Advanced OLAP Visualization of Multidimensional Data Cubes", International Journal of Data Warehousing and Mining, Vol. 3, No. 4, pp. 1--30, 2007.
• 8: Alfredo Cuzzocrea , Wei Wang, Approximate range---sum query answering on data cubes with probabilistic guarantees, Journal of Intelligent Information Systems, v.28 n.2, p.161-197, April 2007 [doi>10.1007/s10844-006-0007-y]
• 9: 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
• 10: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 11: 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
• 12: S. Mansmann, and M. H. Scholl, "Extending Visual OLAP for Handling Irregular Dimensional Hierarchies", Proceedings of 8^th International Conference on Data Warehousing and Knowledge Discovery, pp. 95--105, 2006.
• 13: Torben Bach Pedersen , Christian S. Jensen , Curtis E. Dyreson, The TreeScape System: Reuse of Pre-Computed Aggregates over Irregular OLAP Hierarchies, Proceedings of the 26th International Conference on Very Large Data Bases, p.595-598, September 10-14, 2000
• 14: T. B. Pedersen, C. Jensen, and C. E. Dyreson, "Pre-Aggregation for Irregular OLAP Hierarchies with the TreeScape System", Proceedings of the 17^th IEEE International Conference on Data Engineering,. pp. 1--3, 2001.
• 15: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 16: Transaction Processing Council, TPC Benchmark H, available at http://www.tpc.org/tpch/, 2006.
• 17: University of California, Irvine, 1990 US Census Data, available at http://kdd.ics.uci.edu/databases/census1990/USCensus1990.html, 2001.
• 18: University of California, Irvine, Knowledge Discovery in Databases Archive, available at http://kdd.ics.uci.edu/, 2005.
• 19: Panos Vassiliadis , Timos Sellis, A survey of logical models for OLAP databases, ACM SIGMOD Record, v.28 n.4, p.64-69, Dec.1999 [doi>10.1145/344816.344869]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
OLAP, data cube compression, histograms, semantics