Multidimensional Sparse Array Storage for Data Analytics
Ekow J. Otoo, Hairong Wang, Gideon Nimako · 2016
A relational table over a set of attributes can be mapped onto a multi-dimensional array and stored as such. Such a conceptual view of relations lends itself to easy formulations of numerous analytical algorithms. This is the view taken in the representation of relations in data-warehousing to support On-Line Analytical Processing (OLAP). The main drawback of such a storage scheme is that the equivalent array is typically a highly sparse multi-dimensional array with dominating null entries, and requires a storage scheme with high compression scheme that retains the significant non-null elements. We introduce, analyse and compare the performances of some storage schemes for Multi-Dimensional Sparse Arrays (MDSAs). We first introduce a previously known method called Bit Encoded Sparse Storage (BESS) and then introduce four new storage schemes namely, Patricia trie compressed storage (PTCS), extended compressed row storage (xCRS), bit encoded compressed row storage (BxCRS) and a hybrid storage scheme (Hybrid), that combines the two methods of BESS and xCRS. The performances of these storage schemes are compared with respect to their compression ratios and computational efficiency for accessing an element, retrieving sub-array elements and computing aggregate functions and other analytic functions. We focus primarily on the aggregate function of summation of sub-array elements in this paper. The results show that xCRS, BxCRS, Hybrid and BESS can achieve compression ratios of less than 40% for MDSAs with more than 80% sparsity. The BESS storage scheme gives the best performance in computing multi-dimensional aggregates, for varying sparsity and dimensionality, compared with the other schemes. The key virtue of PTCS is that it is the only scheme that allows for insertions and deletions without reorganising the entire storage previously allocated.