2005/12/13 by Owen Kaser, Daniel Lemire · 1 citation
Computer Science · Mathematics · #Advanced Data Storage Technologies #Advanced Database Systems and Queries #Algorithm #Caching and Content Delivery #Combinatorics #Computer science #Cube (algebra) #Data cube #Data mining #Data warehouse #Dimension (graph theory) #Heuristics #Mathematics #Multidimensional data #Normalization (sociology) #Online analytical processing #cs.DB
paper · pdf · doi:10.1016/j.ins.2005.09.005
published as Owen Kaser, Daniel Lemire, Attribute Value Reordering For Efficient Hybrid OLAP, Information Sciences, Volume 176, Issue 16, 2006, Pages 2304-2336
openalex publication_date 2005/12/13 · arxiv created 2007/02/24 · arxiv updated 2012/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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(d n log(n)) for data cubes of size nd. When dimensions are not independent, we propose and evaluate 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.