Improving Main Memory Utilization for Array-Based DataCube Computation.

Seigo Muto, Masaru Kitsuregawa: Improving Main Memory Utilization for Array-Based DataCube Computation. DOLAP 1998: 28-33
  author    = {Seigo Muto and
               Masaru Kitsuregawa},
  title     = {Improving Main Memory Utilization for Array-Based DataCube Computation},
  booktitle = {DOLAP '98, ACM First International Workshop on Data Warehousing
               and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings},
  publisher = {ACM},
  year      = {1998},
  pages     = {28-33},
  ee        = {db/conf/dolap/MutoK98.html,},
  crossref  = {DBLP:conf/dolap/98},
  bibsource = {DBLP,}


Computing datacubes requires multidimensional aggregations for all possible combinations of each dimension. In this paper, we present a method to improve main memory utilization efficiency for an array-based algorithm for datacube computation in a MOLAP context. The problem with the array-based algorithm is in its sparsity, where a large proportion of array cells are empty. The algorithm proposed in [ZDN97] reduces this space inefficiency by compressing arrays on disk. We improve on this algorithm by performing compression of arrays in main memory as well as on disk using a hashing method, which allocates main memory according to the number of non-empty array cells. We further improve the algorithm using a dynamic main memory allocation strategy. The algorithm by [ZDN97] computes the multiple aggregate views simultaneously, which consumes a lot of main memory space. We propose a main memory allocation method that minimizes the main memory requirement by dynamically allocating main memory only to necessary aggregate views at run time. These savings in main memory resources result in the reduction of disk I/O cost. We evaluate the performance of the proposed method by disk I/O analysis and demonstrate that the improved MOLAP algorithm compares well with a ROLAP algorithm.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

DOLAP '98, ACM First International Workshop on Data Warehousing and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings. ACM 1998
Contents BibTeX

Online Edition

Citation Page BibTeX


Sameet Agarwal, Rakesh Agrawal, Prasad Deshpande, Ashish Gupta, Jeffrey F. Naughton, Raghu Ramakrishnan, Sunita Sarawagi: On the Computation of Multidimensional Aggregates. VLDB 1996: 506-521 BibTeX
Jim Gray, Adam Bosworth, Andrew Layman, Hamid Pirahesh: Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total. ICDE 1996: 152-159 BibTeX
Kenneth A. Ross, Divesh Srivastava: Fast Computation of Sparse Datacubes. VLDB 1997: 116-125 BibTeX
Yihong Zhao, Prasad Deshpande, Jeffrey F. Naughton: An Array-Based Algorithm for Simultaneous Multidimensional Aggregates. SIGMOD Conference 1997: 159-170 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
DOLAP 1998 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:07:20 2009