Using Chunked Extendible Array for Physical Storage of Scientific Datasets

摘要

The data model found to be most appropriate for scientific databases is the emph{array-oriented data model.} This also forms the basis of storing and accessing the database onto and from physical storage. Such storage systems are exemplified by the hierarchical data format(HDF/HDF5), the network common data format (NetCDF) and recently the SciDB. Given that the array is mapped onto linear locations in a file, i.e., a representation of an array file, in either row-major or column-major order, a fundamental feature of the representation is that they should be allowed to grow to massively large sizes by gradual expansions of the array bounds. In both the row-major and column-major order of array elements, extendibility is allowed in one dimension only. We present an approach of storing multi-dimensional dense array on physical storage devices, that allows arbitrary extensions of any of the array bounds, without reorganising previously allocated array elements. For a $k$-dimensional $N$-element array, the organisation allows an element to be accessed in time $O(k + log N)$ using $O(k^2 N^{1/k})$ additional space. By chunking the array to size $N_c$ chunks, the time and space requirements reduce to $O(k + log N_c)$ and $O(k^2 N_c^{1/k}).$