Efficient storage scheme for n-dimensional sparse array: GCRS/GCCS
Md Abu Hanif Shaikh, K. M. Azharul Hasan · 2015
Degree of data sparsity increases with the increase of number of dimensions in high performance scientific computing. Storing and applying operations on this highly sparse multidimensional data is still a challenge for data scientists. Experts suggest special storage scheme over sparse array. In traditional sparse array storage scheme, (n+l) one dimensional arrays are necessary to store n-dimensional array. In this paper, we propose `Generalized Row/Column Storage (GCRS/GCCS)' scheme which requires three one dimensional arrays only for storing a n-dimensional array. The superiority of the GCRS/GCCS over traditional Compressed Row/Column Storage (CRS/CCS) is shown by both theoretical analysis and experimental results. In theoretical analysis, we derive equations for space and time complexity as well as the range of usability for GCRS/GCCS. It is shown that the GCRS/GCCS scheme yields to support minimum 50% data density where as the range of usability is inversely proportional with the number of dimensions for CRS/CCS scheme. The experimental result shows that the proposed GCRS/GCCS scheme outperforms the CRS/CCS scheme with respect to space complexity, time complexity and range of usability.