Attribute Value Reordering for Efficient Hybrid OLAP

Download
  1. (PDF, 284 KB)
AuthorSearch for: ; Search for:
TypeArticle
ConferenceThe Sixth International Workshop on Data Warehousing and OLAP (DOLAP'03), November 7, 2003., New Orleans, Louisiana, USA
Subjectdata cubes; normalization; chunking; multidimensional binary arrays; OLAP; MOLAP
AbstractThe normalization of a data cube is the process of choosing an ordering for the attribute values, and the chosen ordering will affect the physical storage of the cube's data. For large multidimensional arrays, proper normalization can lead to more efficient storage in hybrid OLAP contexts that store dense and sparse chunks differently. We show that it is NP-hard to compute an optimal normalization even for 1×3 chunks, although we find an exact algorithm for 1×2 chunks. When attributes are nearly statistically independent, we show that an optimal normalization is given by dimension-wise attribute frequency sorting, which can be done in time O(<em>dn</em>log(<em>n</em>)) for data cubes of size <em>n<sup>d</sup></em> . When attributes are not independent, we propose and evaluate a number of heuristics.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.
Publication date
LanguageEnglish
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number46510
NPARC number5765320
Export citationExport as RIS
Report a correctionReport a correction
Record identifier5de58bb0-1836-41b1-9308-d2d95b0435a2
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)