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

3rd STDBM Workshop on Spatio-Temporal Database Management

Ekow J. Otoo ; Doron Rotem

Others  :  http://CEUR-WS.org/Vol-174/paper9.pdf
PID  :  12059

来源: CEUR

【 摘 要 】

Large scale scientific datasets are generally modeled as k-dimensional arrays, since this model is amenable to the form of analyses and visualization of the scientific phenomenon often investigated. In recent years, organizations have adopted the use of on-line analytical processing (OLAP), methods and statistical analyses to make strategic 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 array elements are allocated in a sequence of consecutive locations according to an ordering of array mapping functions that map k-dimensional indices 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 reorganizing previously allocated elements. We give a mapping function F∗(), and its inverse F −1∗ (), for computing the linear address of an array element given its k-dimensional index. The technique 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 implementation gives an efficient storage scheme for both scientific and OLAP multi-dimensional datasets that are allowed to incrementally grow without incurring the prohibitive costs of reorganizations.