A secondary storage scheme for multidimensional data preserving proximity

Multidimensional arrays storing multidimensional data in MOLAP are usually very sparse. They also suffer from the problem that the time consumed in sequential access to array elements heavily depends on the dimension along which elements are accessed. This dimension dependency would be caused by arranging multidimensional data in linear order on secondary storage and the logical proximity among the multidimensional data would be lost in physical storage. This situation can be alleviated by dividing the whole array into the set of subarrays called "chunks". However, further dimension dependency would be caused, unless the compressed chunks are arranged judiciously in the page buffer. The difference among the dimension cardinalities could also cause dimension dependency; slice operation along a dimension of large cardinality tends to consume much time. We will alleviate these two kinds of dimension dependency by introducing the notion of an "extended chunk". Extended chunks can contribute to preserve the logical proximity by adapting flexibly to the usual situation where data densities are very low and are not uniformly distributed. Based on extended chunks, we will propose secondary storage schemes for multidimensional datasets using a space-filling curve such as Z-curve. The evaluation result shows that the proposed storage schemes exhibit better performance while alleviating the dimension dependency.