Article

Hierarchical dwarfs for the rollup cube

Authors:

Yannis Sismanis,

Antonios Deligiannakis,

Yannis Kotidis,

Nick RoussopoulosAuthors Info & Claims

DOLAP '03: Proceedings of the 6th ACM international workshop on Data warehousing and OLAP

Pages 17 - 24

https://doi.org/10.1145/956060.956064

Published: 07 November 2003 Publication History

Abstract

The data cube operator exemplifies two of the most important aspects of OLAP queries: aggregation and dimension hierarchies. In earlier work we presented Dwarf, a highly compressed and clustered structure for creating, storing and indexing data cubes. Dwarf is a complete architecture that supports queries and updates, while also including a tunable granularity parameter that controls the amount of materialization performed. However, it does not directly support dimension hierarchies. Rollup and drilldown queries on dimension hierarchies that naturally arise in OLAP need to be handled externally and are, thus, very costly. In this paper we present extensions to the Dwarf architecture for incorporating rollup data cubes, i.e. cubes with hierarchical dimensions. We show that the extended Hierarchical Dwarf retains all its advantages both in terms of creation time and space while being able to directly and efficiently support aggregate queries on every level of a dimension's hierarchy.

References

[1]

S. Acharya, P. B. Gibbons, and V. Poosala. Congressional Samples for Approximate Answering of Group-By Queries. In Proc. of ACM SIGMOD, pages 487--498, Dallas, Texas, 2000.

Digital Library

[2]

S. Agarwal, R. Agrawal, P. M. Deshpande, A. Gupta, J. F. Naughton, R. Ramakrishnan, and S. Sarawagi. On the computation of multidimensional aggregates. In Proc. of VLDB, pages 506--521, 1996.

Digital Library

[3]

E. Baralis, S. Paraboschi, and E. Teniente. Materialized View Selection in a Multidimensional Data base. In Proc. of VLDB, pages 156--165, Athens, Greece, August 1997.

Digital Library

[4]

K. Beyer and R. Ramakrishnan. Bottom- Up Computation of Sparse and Iceberg CUBEs. In Proc. of ACM SIGMOD, pages 359--370, Philadelphia, PA, USA, 1999.

Digital Library

[5]

S. Chaudhuri and U. Dayal. An Overview of Data Warehousing and OLAP Technology. SIGMOD Record, 26 1, September 1997.

Digital Library

[6]

P. Deshpande, S. Agarwal, J. Naughton, and R. Ramakrishnan. Computation of multidimensional aggregates. Technical Report 1314, University of Wisconsin-Madison, 1996.

[7]

M. Ester, J. Kohlhammer, and H.- P. Kriegel. The DC-Tree: A Fully Dynamic Index Structure for Data Warehouses. In Proc. of ICDE, pages 379--388, San Diego, California, 2000.

Digital Library

[8]

L. Fu and J. Hammer. CUBIST: A New Algorithm for Improving the Performance of Ad- hoc OLAP Queries. In DOLAP, 2000.

Digital Library

[9]

J. Gray, A. Bosworth, A. Layman, and H. Piramish. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. In Proc. of ICDE, pages 152--159, New Orleans, February 1996. IEEE.

Digital Library

[10]

H. Gupta, V. Harinarayan, A. Rajaraman, and J. Ullman. Index Selection for OLAP. In Proc. of ICDE, pages 208--219, Burmingham, UK, April 1997.

Digital Library

[11]

V. Harinarayan, A. Rajaraman, and J. Ullman. Implementing Data Cubes Efficiently. In Proc. of ACM SIGMOD, pages 205--216, Montreal, Canada, June 1996.

Digital Library

[12]

J. Hellerstein, P. Haas, and H. Wang. Online Aggregation. In Proc. of ACM SIGMOD, pages 171--182, Tucson, Arizona, May 1997.

Digital Library

[13]

H. V. Jagadish, L. Lakshmanan, and D. Srivastava. What can Hierarchies do for Data Warehouses? In Proc. of VLDB, pages 530--541, Edinburgh, Scotland, September 1999.

Digital Library

[14]

T. Johnson and D. Shasha. Some Approaches to Index Design for Cube Forests. Data Engineering Bulletin, 20(1):27--35, March 1997.

[15]

H. J. Karloff and M. Mihail. On the Complexity of the View- Selection Problem. In Proc. of Symposium on Principles of Database Systems, pages 167--173, Philadelphia, Pennsylvania, May 1999.

Digital Library

[16]

L. Lakshmanan, J. Pei, and Y. Zhao. QC-Trees: An Efficient Summary Structure for Semantic OLAP. In Proc. of ACM SIGMOD, pages 64--75, San Diego, California, 2003.

Digital Library

[17]

K. A. Ross and D. Srivastana. Fast Computation of Sparse Datacubes. In Proc. of VLDB, pages 116--125, Athens, Greece, 1997.

Digital Library

[18]

N. Roussopoulos. View Indexing in Relational Databases. ACM Trans. Database Syst., 7(2):258--290, June 1982.

Digital Library

[19]

N. Roussopoulos, Y. Kotidis, and M. Roussopoulos. Cubetree: Organization of and Bulk Incremental Updates on the Data Cube. In Proc. ACM SIGMOD, pages 89--99, Tucson, Arizona, May 1997.

Digital Library

[20]

S. Sarawagi, R. Agrawal, and A. Gupta. On computing the data cube. Technical Report RJ10026, IBM Almaden Research Center, San Jose, CA, 1996.

[21]

Y. Sismanis, A. Deligiannakis, N. Roussopoulos, and Y. Kotidis. Dwarf: Shrinking the PetaCube. In Proc. ACM SIGMOD, pages 464--475, Madison, Wisconsin, 2002.

Digital Library

[22]

D. Theodoratos and T. Sellis. Data Warehouse Configuration. In Proc. of VLDB, pages 126--135, Athens, Greece, August 1997.

Digital Library

[23]

P. Vassiliadis and T. Sellis. A Survey of Logical Models for OLAP Databases. SIGMOD Record, 28(4):64--69, 1999.

Digital Library

[24]

J. Vitter, M. Wang, and B. Iyer. Data Cube Approximation and Histograms via Wavelets. In Proc. of CIKM, 1998.

Digital Library

[25]

W. Wang, H. Lu, J. Feng, and J. X. Yu. Condensed Cube: An Effective Approach to Reducing Data Cube Size. In Proc. of ICDE, 2002.

Digital Library

[26]

Y. Zhao, P. M. Deshpande, and J. F. Naughton. An array-based algorithm for simultaneous multidimensional aggregates. In Proc. of ACM SIGMOD, pages 159--170, 1997.

Digital Library

Cited By

Roy SMitra MDe SMukherjee S(2024)Enhanced Methodology for Boosting Employee Retention Through Various ML and Data Engineering MethodsRecent Trends in Intelligence Enabled Research10.1007/978-981-97-2321-8_1(1-9)Online publication date: 16-May-2024
https://doi.org/10.1007/978-981-97-2321-8_1
Wijaya ANugraha ASukmono A(2023)Study on the Use of Multidimensional Database Systems for Demography Data AnalysisE3S Web of Conferences10.1051/e3sconf/202344802060448(02060)Online publication date: 17-Nov-2023
https://doi.org/10.1051/e3sconf/202344802060
Liu CWu CShao HYuan X(2019)SmartCube: An Adaptive Data Management Architecture for the Real-Time Visualization of Spatiotemporal DatasetsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.2934434(1-1)Online publication date: 2019
https://doi.org/10.1109/TVCG.2019.2934434
Show More Cited By

Index Terms

Hierarchical dwarfs for the rollup cube
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
    2. Information integration
      1. Data warehouses
  2. Information systems applications
    1. Decision support systems
      1. Data warehouses

Recommendations

Parallel querying of ROLAP cubes in the presence of hierarchies
DOLAP '05: Proceedings of the 8th ACM international workshop on Data warehousing and OLAP

Online Analytical Processing is a powerful framework for the analysis of organizational data. OLAP is often supported by a logical structure known as a data cube, a multidimensional data model that offers an intuitive array-based perspective of the ...
Approximate Query Processing in Cube Streams

Data cubes have become important components in most data warehouse systems and Decision-Support-Systems. In such systems, users usually pose very complex queries to the Online Analytical Processing (OLAP) system, and systems usually have to deal with a ...
Minimized-cost cube query on heterogeneous information networks

Data cube is the foundation of on-line analytical processing (OLAP), which can provide users with data views from different perspectives and granularities. Heterogeneous information networks consist of multiple types of nodes and edges which represent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DOLAP '03: Proceedings of the 6th ACM international workshop on Data warehousing and OLAP

November 2003

104 pages

ISBN:1581137273

DOI:10.1145/956060

Program Chairs:
Stefano Rizzi
University of Bologna, Italy
,
Il-Yeol Song
College of Information Science and Technology, USA

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM03

Sponsor:

CIKM03: 12th International Conference on Information and Knowledge Management

November 7, 2003

Louisiana, New Orleans, USA

Acceptance Rates

Overall Acceptance Rate 29 of 79 submissions, 37%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
837
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roy SMitra MDe SMukherjee S(2024)Enhanced Methodology for Boosting Employee Retention Through Various ML and Data Engineering MethodsRecent Trends in Intelligence Enabled Research10.1007/978-981-97-2321-8_1(1-9)Online publication date: 16-May-2024
https://doi.org/10.1007/978-981-97-2321-8_1
Wijaya ANugraha ASukmono A(2023)Study on the Use of Multidimensional Database Systems for Demography Data AnalysisE3S Web of Conferences10.1051/e3sconf/202344802060448(02060)Online publication date: 17-Nov-2023
https://doi.org/10.1051/e3sconf/202344802060
Liu CWu CShao HYuan X(2019)SmartCube: An Adaptive Data Management Architecture for the Real-Time Visualization of Spatiotemporal DatasetsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.2934434(1-1)Online publication date: 2019
https://doi.org/10.1109/TVCG.2019.2934434
Golfarelli MRizzi S(2017)From Star Schemas to Big Data: 20 $$+$$ Years of Data Warehouse ResearchA Comprehensive Guide Through the Italian Database Research Over the Last 25 Years10.1007/978-3-319-61893-7_6(93-107)Online publication date: 31-May-2017
https://doi.org/10.1007/978-3-319-61893-7_6
Ahmed UTchounikine AMiquel M(2014)Dynamic cubing for hierarchical multidimensional data spaceJournal of Decision Systems10.1080/12460125.2014.94024123:4(415-436)Online publication date: Aug-2014
https://doi.org/10.1080/12460125.2014.940241
Lins LKlosowski JScheidegger C(2013)Nanocubes for Real-Time Exploration of Spatiotemporal DatasetsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.17919:12(2456-2465)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1109/TVCG.2013.179
Eavis TTaleb A(2012)Query Optimization and Execution in a Parallel Analytics DBMSProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.85(897-908)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.85
Ahmed UTchounikine AMiquel MServigne S(2010)Real-time temporal data warehouse cubingProceedings of the 21st international conference on Database and expert systems applications: Part II10.5555/1887568.1887585(159-167)Online publication date: 30-Aug-2010
https://dl.acm.org/doi/10.5555/1887568.1887585
Eavis TTabbara HTaleb A(2010)The NOX frameworkProceedings of the 12th international conference on Data warehousing and knowledge discovery10.5555/1881923.1881942(172-189)Online publication date: 30-Aug-2010
https://dl.acm.org/doi/10.5555/1881923.1881942
Asiki ATsoumakos DKoziris N(2010)Distributing and searching concept hierarchiesCluster Computing10.1007/s10586-010-0136-513:3(257-276)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1007/s10586-010-0136-5
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents