arXiv preprint ·
Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization
An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
The Complexity of Value Optimization in Sporadic Task Systems
Uniformity Testing for the Monomer-Dimer Model
Linear Hashing Is Poissonesque
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.