Title :
Improvement of a row displacement algorithm for sparse table compression
Author :
Arita, Takeshi ; Koyama, Masashi ; Shishibori, Masami ; Aoe, Jun-Ichi
Author_Institution :
Dept. of Inf. Sci. & Intelligent Syst., Tokushima Univ., Japan
Abstract :
A row displacement method compresses efficiently a sparse matrix into a one-dimensional array. The access time with this method is O(1), but the application was restricted to the static matrices. In order to extend the use of the row displacement method to the dynamic matrices, the algorithms for insertion and deletion are proposed and the efficiency is confirmed by theoretical and empirical observations
Keywords :
computational complexity; matrix algebra; 1D array; access time; dynamic matrices; row displacement algorithm; sparse matrix compression; sparse table compression; Automata; Circuits; Data structures; Information science; Intelligent systems; Pattern matching; Petroleum; Sparse matrices; Storage automation; Tree graphs;
Conference_Titel :
Systems, Man, and Cybernetics, 1996., IEEE International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7803-3280-6
DOI :
10.1109/ICSMC.1996.565365