Compression methods speed up math operations on large sparse matrices
Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra
Data Structures and Algorithms
Summary
Large datasets like social networks are often stored as big grids called matrices. These matrices usually have lots of empty spots, so people compress them to save space. But normally, you have to uncompress them before doing math, which wastes time. The authors review different clever ways to compress these matrices that also let you do math directly on the compressed data, saving time and space. They organize these methods by the kind of patterns each one uses and explain how they work and compare.
What this means in practice
- •For machine learning engineers: Run math operations faster on compressed data in large feature matrices used by machine learning models to reduce memory and computational costs.
- •For graph database developers: Speed up queries involving relations stored as sparse matrices by performing algebraic computations directly on compressed graph data.
A survey. It maps existing work.
Authors
Gonzalo Navarro
Abstract
Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies \emph{computation-friendly} compression: formats that are not only small, but let us carry out matrix--vector products, and in some cases matrix--matrix products, sums and closures, directly on the compressed representation {\em in time proportional to that compressed size}. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros ($k^2$-trees and their variants), similarity between rows (Boldi--Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the representation, the algorithms, the theoretical guarantees and the empirical performance. Further, we show that the last three families are instances of a single general scheme, which we call a {\em sparse straight-line factorization} of the matrix, whose forward and backward substitutions evaluate right and left products in time proportional to the size of the representation, and that the product of two such factorizations is again one, which gives matrix--matrix products with a compressed output. An appendix reviews formats that must be decompressed (at least partially) before operating, for completeness. We close with a cross-family comparison and a list of open problems.