TY - JOUR
T1 - Efficient Data Compression Methods for Multidimensional Sparse Array Operations Based on the EKMR Scheme
AU - Lin, Chun Yuan
AU - Chung, Yeh Ching
AU - Liu, Jen Shiuh
PY - 2003/12
Y1 - 2003/12
N2 - 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.
AB - 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.
KW - Data compression scheme
KW - Karnaugh map
KW - Multidimensional sparse array
KW - Sparse array operation
KW - Sparse ratio
UR - http://www.scopus.com/inward/record.url?scp=0348011367&partnerID=8YFLogxK
U2 - 10.1109/TC.2003.1252859
DO - 10.1109/TC.2003.1252859
M3 - 文章
AN - SCOPUS:0348011367
SN - 0018-9340
VL - 52
SP - 1640
EP - 1646
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 12
ER -