
ALT 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 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 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²-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 repre




























