A Storage Scheme for Multi-dimensional Databases Using Extendible Array Files

Large scale scientific datasets are generally mod-eled as k-dimensional arrays, since this model is amenable to the form of analyses and visualiza-tion of the scientific phenomenon often investi-gated. In recent years, organizations have adopted the use of on-line analytical processing (OLAP), methods and statistical analyses to make strate-gic business decisions using enterprise data that are modeled as multi-dimensional arrays as well. In both of these domains, the datasets have the propensity to gradually grow, reaching orders of terabytes. However, the storage schemes used for these arrays correspond to those where the ar-ray elements are allocated in a sequence of con-secutive locations according to an ordering of ar-ray mapping functions that map k-dimensional in-dices one-to-one onto the linear locations. Such schemes limit the degree of extendibility of the ar-ray to one dimension only. We present a method of allocating storage for the elements of a dense multidimensional extendible array such that the bounds on the indices of the respective dimen-sions can be arbitrarily extended without reorga-nizing previously allocated elements. We give a mapping function F∗(), and its inverse F −1 for computing the linear address of an array el-ement given its k-dimensional index. The tech-nique adopts the mapping function, for realizing an extendible array with arbitrary extendibility in main memory, to implement such array files. We show how the extendible array file implementa-tion gives an efficient storage scheme for both sci-entific and OLAP multi-dimensional datasets that are allowed to incrementally grow without incur-ring the prohibitive costs of reorganizations