What Is Wrong With CVS?
While researching on compressed sparse matrix, I stumbled upon compressed row storage (CRS; compressed sparse row, CSR; Yale format) and compressed column storage (CCS; compressed sparse column, CSC). These sparse matrix compression formats are popular. Stepping back and imagining the possibilities, I considered the possibility of applying basic lossless compression techniques to sparse matrices, exploiting data redundancy, leading to what I call the compressed value storage (CVS).
CRS compresses on row information. CCS compresses on column information. CRS and CCS share many similarities, including compression ratio and space savings. Depending on the sparse matrix data, CRS or CCS can be better or worse in performing various matrix operations when compared to each other. There are tradeoffs, which by itself is perfect! They are important inspirations. You see, they prove that a sparse matrix compression algorithm doesn't have to be the best. It just needs to be good and special at some (if not most) things about matrices.
CVS compresses sparse matrices in two places: the value, by storing only one copy of distinct non-zero values; and the coordinates, by storing them as linear indexes (instead of a pair of row and column integers). These features can allow CVS to achieve better compression ratio and space savings than CRS/CCS. Now this is both an advantage and a disadvantage. For starters, any "better" compression can potentially be more complicated to work with. Granted, and if you agree that CVS compression is better than CRS/CCS, how much more complicated is CVS to work with?
If you try to search online for any sparse matrix compression material that is similar to CVS, you can't find any. At least based on my searches. Perhaps they are out there, I just can't find them. If there are any after all, why isn't CVS (or that like it) as popular as CRS and CCS? It makes me wonder. The concept of CVS is simple. It is so simple, and un-talked about, it makes me question its practical value. Was it ever raised before and junked by the community or experts? What is wrong with CVS?
If there is anyone out there who can study CVS and put some "Math" to it, so to speak, then perhaps its purpose can be better defined once and for all. How does CVS "really" compare and measure up to CRS/CCS? Where can CVS be used best? Why use CVS? In the first place, should CVS even be taken seriously?
CRS compresses on row information. CCS compresses on column information. CRS and CCS share many similarities, including compression ratio and space savings. Depending on the sparse matrix data, CRS or CCS can be better or worse in performing various matrix operations when compared to each other. There are tradeoffs, which by itself is perfect! They are important inspirations. You see, they prove that a sparse matrix compression algorithm doesn't have to be the best. It just needs to be good and special at some (if not most) things about matrices.
CVS compresses sparse matrices in two places: the value, by storing only one copy of distinct non-zero values; and the coordinates, by storing them as linear indexes (instead of a pair of row and column integers). These features can allow CVS to achieve better compression ratio and space savings than CRS/CCS. Now this is both an advantage and a disadvantage. For starters, any "better" compression can potentially be more complicated to work with. Granted, and if you agree that CVS compression is better than CRS/CCS, how much more complicated is CVS to work with?
If you try to search online for any sparse matrix compression material that is similar to CVS, you can't find any. At least based on my searches. Perhaps they are out there, I just can't find them. If there are any after all, why isn't CVS (or that like it) as popular as CRS and CCS? It makes me wonder. The concept of CVS is simple. It is so simple, and un-talked about, it makes me question its practical value. Was it ever raised before and junked by the community or experts? What is wrong with CVS?
If there is anyone out there who can study CVS and put some "Math" to it, so to speak, then perhaps its purpose can be better defined once and for all. How does CVS "really" compare and measure up to CRS/CCS? Where can CVS be used best? Why use CVS? In the first place, should CVS even be taken seriously?
Mathematics is not about numbers, equations, computations, or algorithms. It is about understanding. -- William Paul Thurston
Comments
Post a Comment