Paper Info
Title
Attribute value reordering for efficient hybrid OLAP
Abstract
The normalization of a data cube is the ordering of the attribute values. For large multidimensional arrays where dense and sparse chunks are stored differently, proper normalization can lead to improved storage efficiency. We show that it is NP-hard to compute an optimal normalization even for 1x3 chunks, although we find an exact algorithm for 1x2 chunks. When dimensions are nearly statistically independent, we show that dimension-wise attribute frequency sorting is an optimal normalization and takes time O(dnlog(n)) for data cubes of size n^d. When dimensions are not independent, we propose and evaluate a several heuristics. The hybrid OLAP (HOLAP) storage mechanism is already 19-30% more efficient than ROLAP, but normalization can improve it further by 9-13% for a total gain of 29-44% over ROLAP.
Year
DOI
Venue
2007
10.1016/j.ins.2005.09.005
Information Sciences: an International Journal
Keywords
Field
DocType
attribute value reordering,improved storage efficiency,large multidimensional array,dimension-wise attribute frequency,attribute value,storage mechanism,efficient hybrid olap,optimal normalization,hybrid olap,proper normalization,exact algorithm,data cube,olap,chunking,statistical independence,data cubes,normalization
Data mining,Normalization (statistics),Computer science,HOLAP,Theoretical computer science,MOLAP,Chunking (psychology),ROLAP,Online analytical processing,Database,Data cube
Journal
Volume
Issue
ISSN
abs/cs/0702143
16
Owen Kaser, Daniel Lemire, Attribute Value Reordering For Efficient Hybrid OLAP, Information Sciences, Volume 176, Issue 16, 2006, Pages 2304-2336
ISBN
Citations 
PageRank 
1-58113-727-3
11
0.65
References 
Authors
16
2
Name
Order
Citations
PageRank
Owen Kaser132524.02
Daniel Lemire282152.14