Efficient Data Compression Methods for Multidimensional Sparse Array Operations Based on the EKMR Scheme

摘要

[[abstract]]In our previous work, we have proposed the extended Karnaugh map representation (EKMR) scheme for multidimensional array representation. In this paper, we propose two data compression schemes, EKMR Compressed Row/Column Storage (ECRS/ECCS), for multidimensional sparse arrays based on the EKMR scheme. To evaluate the proposed schemes, we compare them to the CRS/CCS schemes. Both theoretical analysis and experimental tests were conducted. In the theoretical analysis, we analyze the CRS/CCS and the ECRS/ECCS schemes in terms of the time complexity, the space complexity, and the range of their usability for practical applications. In experimental tests, we compare the compressing time of sparse arrays and the execution time of matrix-matrix addition and matrix-matrix multiplication based on the CRS/CCS and the ECRS/ ECCS schemes. The theoretical analysis and experimental results show that the ECRS/ECCS schemes are superior to the CRS/CCS schemes for all the evaluated criteria, except the space complexity in some cases.