Value-Compressed Sparse Column (VCSC): Sparse Matrix Storage for Redundant Data
This provides a broadly useful solution for encoding and reading redundant sparse data, particularly in domains like genomics, though it is incremental as it builds on existing CSC formats.
The paper tackles the problem of storing highly redundant sparse matrices, which are common in machine learning applications like genomics and often too large for in-core computation with conventional formats, by introducing VCSC and IVCSC extensions to CSC that achieve up to 10-fold memory reduction over COO with minimal performance impact.
Compressed Sparse Column (CSC) and Coordinate (COO) are popular compression formats for sparse matrices. However, both CSC and COO are general purpose and cannot take advantage of any of the properties of the data other than sparsity, such as data redundancy. Highly redundant sparse data is common in many machine learning applications, such as genomics, and is often too large for in-core computation using conventional sparse storage formats. In this paper, we present two extensions to CSC: (1) Value-Compressed Sparse Column (VCSC) and (2) Index- and Value-Compressed Sparse Column (IVCSC). VCSC takes advantage of high redundancy within a column to further compress data up to 3-fold over COO and 2.25-fold over CSC, without significant negative impact to performance characteristics. IVCSC extends VCSC by compressing index arrays through delta encoding and byte-packing, achieving a 10-fold decrease in memory usage over COO and 7.5-fold decrease over CSC. Our benchmarks on simulated and real data show that VCSC and IVCSC can be read in compressed form with little added computational cost. These two novel compression formats offer a broadly useful solution to encoding and reading redundant sparse data.