Abstract
In this paper, we propose a sound approach and an algorithm 1 for computing a condensed representation of either full or iceberg datacubes. A novel characterization of datacubes based on dimensional-measurable partitions is introduced. From such partitions, iceberg cuboids are achieved by using constrained product linearly in the number of tuples. Moreover, our datacube characterization provides a loss-less condensed representation specially suitable when considering the storage explosion problem and the I/O cost. We show that our algorithm Ccube turns out to an operational solution more efficient than competive proposals. It enforces a lecticwise and recursive traverse of the dimension set lattice and takes into account the critical problem of memory limitation. Our experimental results shows that Ccube is a promising candidate for scalable computation.
This work is partially supported by the AS CNRS-STIC “Data Mining”
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Agarwal, R. Agrawal, P. Deshpande, A. Gupta, J.F. Naughton, R. Ramakrishnan, and S. Sarawagi. On the Computation of Multidimensional Aggregates. In VLDB’96, pages 506–521, 1996.
D. Barbará and M. Sullivan. Quasi-Cubes: Exploiting Approximations in Multidimensional Databases. SIGMOD Record, 26(3):12–17, 1997.
K.S. Beyer and R. Ramakrishnan. Bottom-Up Computation of Sparse and Iceberg CUBEs. In A CM SIGMOD, USA, pages 359–370, 1999.
G. Dong, J. Han, J. M. W. Lam, J. Pei, and K. Wang. Multi-Dimensional Constrained Gradients in Data Cubes. In VLDB’01, pages 321–330, Italy, 2001.
M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J.D. Ullman. Computing Iceberg Queries Efficiently. In VLDB’98, New York City, New York, USA, pages 299–310. Morgan Kaufmann, 1998.
B. Ganter and K. Reuter. Finding all Closed Sets: A General Approach. Order, 8:283–290, 1991.
B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundations. Springer-Verlag, 1999.
J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Mining and Knowledge Discovery, 1(1), 1997.
J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2001.
J. Han, J. Pei, G. Dong, and K. Wang. Efficient Computation of Iceberg Cubes with Complex Measures. In ACM SIGMOD’01, USA, 2001.
V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing data cubes efficiently. In A CM SIGMOD’96, pages 205–216, Montreal, Quebec, Canada, June 1996.
A. C. Klug. Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. Journal of ACM, 29(3):699–717, 1982.
H. Lu and H. Liu. Decision Tables: Scalable Classification Exploring RDBMS Capabilities. In VLDB’00, pages 373–384, Cairo, Egypt, September 2000.
H. Mannila and H. Toivonen. Levelwise Search and Borders of Theories in Knowledge Discovery. Data Mining and Knowledge Discovery, 10(3):241–258, 1997.
K.A. Ross and D. Srivastava. Fast Computation of Sparse Datacubes. In VLDB’97, Athens, Greece, pages 116–125, 1997.
K.A. Ross, D. Srivastava, and D. Chatziantoniou. Complex Aggregation at Mutiple Granularities. In EDBT’98, LNCS vol. 1377, pages 263–277. Springer Verlag, 1998.
K.A. Ross and K.A. Zaman. Serving Datacube Tuples from Main Memory. In SSDM’2000, Berlin, Germany, pages 182–195, 2000.
N. Spyratos. The partition model: A deductive database model. ACM TODS, 12(1):1–37, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Laporte, M., Novelli, N., Cicchetti, R., Lakhal, L. (2002). Computing Full and Iceberg Datacubes Using Partitions. In: Hacid, MS., Raś, Z.W., Zighed, D.A., Kodratoff, Y. (eds) Foundations of Intelligent Systems. ISMIS 2002. Lecture Notes in Computer Science(), vol 2366. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48050-1_28
Download citation
DOI: https://doi.org/10.1007/3-540-48050-1_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43785-7
Online ISBN: 978-3-540-48050-1
eBook Packages: Springer Book Archive