Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra

1 Introduction

• Conventional compressors save space but require decompression for matrix–vector products, adding time and potentially raising peak memory to the uncompressed matrix size.Computation-friendly compression instead targets operation time and working space proportional to the compressed representation.Source: §1 · p. 2
• The survey groups formats by redundancy: spatial clustering, similar rows, repeated substrings, and dense bipartite subgraphs.It presents k2-trees first, then referencing, grammar, and biclique formats; reported experiments use different machines, datasets, and implementations and are not comparable across families.Source: §1 · p. 2
• The survey contrasts k2-trees, which offer broad algebra but less time improvement, with the other families, which report considerable speedups and relevant compression ratios.The experimental figures illustrate trends rather than provide cross-family comparisons.Source: §1 · p. 2
• Referencing, grammar, and biclique formats are sparse straight-line factorizations whose forward and backward substitutions compute right and left products in time proportional to factor nonzeros.Products of two factorizations remain factorized, but output size is not generally bounded, so recompression may be needed.Source: §1 · p. 3

2.1 Notation and operations

• Matrix–vector products are central to iterative solvers, linear-model training and inference, and graph-neural-network propagation; repeated products with one matrix can justify one-time compression effort.The section also identifies matrix–matrix products and transitive closure as important Boolean operations in graph queries, triangle counting, and database queries.Source: §2.1 · pp. 3–4

2.2 Plain sparse formats

• COO, CSR, and CSC store sparse entries explicitly and support vector products in Θ(nnz(A)) time; Boolean sparse-matrix multiplication can use Schoor’s algorithm.For uniformly distributed 1s, Schoor’s algorithm takes O(nnz(A)nnz(B)/n) time on average.Source: §2.2 · p. 4

2.3 What is computation-friendly compression?

• A representation is computation-friendly when an operation runs from it in time and working space O(|C(A)|) plus output size, without materializing A.The survey distinguishes formats by supported operations and whether outputs can remain in the same compressed format; its taxonomy table summarizes these capabilities.Source: §2.3 · p. 4, Table 1 · p. 5

2.4 Lower bounds and what they imply

• Worst-case lower bounds exclude linear-time operations for some compressed inputs, while surveyed guarantees depend on a particular representation being small on suitable instances.For grammar-compressed matrices, explicitly stored column positions let repeated sequences align with the same part of the vector.Source: §2.4 · p. 5

2.5 Computational model

• The analysis uses the word RAM model with Θ(log N)-bit words and succinct trees and bitvectors equipped with rank and select support.Figure 1 illustrates level-by-level signatures for a k2-tree.Source: §2.5 · p. 5, Figure 1 · p. 6

2.6 A taxonomy of computation-friendly formats

• The taxonomy classifies formats by the matrix redundancy they extract and notes that the last three families share a scheme.Table 1 summarizes the covered families and their supported operations.Source: Table 1 · p. 5, §2.6 · p. 6

3 𝑘2-Trees and their Algebra

• The k2-tree supports a Boolean matrix algebra whose operation results remain in the same format.The surveyed work was motivated by graph-database regular path queries.Source: §3 · p. 6

3.1 The k2-tree

• The k2-tree stores a Boolean matrix as recursively partitioned quadrants, using level-wise signatures to mark nonempty regions; clustering can substantially reduce its space.With a nonzero count a, worst-case space is 4a log_4(n^2/a)(1 + o(1)) bits; clustered points admit a smaller bound.Source: §3.1 · p. 6

3.2 Products by a vector

• Vector multiplication traverses only nonempty children and adds input entries to output entries at the 1-cells; the left product is obtained by simulating a transpose.The matrix is padded to a power of two, but the zero padding is never reached.Source: §3.2 · p. 7
• The standard traversal costs O(a log(n^2/a) + n), which is worse than the O(a + n) time of COO, CSR, or CSC despite saving space.For variants marking full quadrants, prefix sums and a binary tree over the output can support products in time proportional to the k2-tree nodes.Source: §3.2 · pp. 7–8

3.3 A Boolean matrix algebra on 𝑘2-trees

• The Boolean algebra returns operation results in k2-tree form, and transposition can be represented by toggling a flag without modifying the tree.The flag is honored by operations on submatrices.Source: §3.3 · p. 8
• Sum is computed by a sequential pass over the trees, while intersection, difference, and symmetric difference recurse over quadrants and can copy empty-operand subtrees.Intersection has an adaptive O(δ log(n^2/δ)) bound, where c ≤ δ ≤ min(a,b).Source: §3.3 · p. 8
• For uniformly distributed 1s, recursive Boolean multiplication takes O(min(a,b) max(a,b) log n) time on average, or O(a^1.5 log n) when a = b.Empty quadrants prune recursion, and sums involving an empty matrix can reuse the product.Source: §3.3 · p. 8
• The proposed transitive-closure algorithm uses O(1) multiplications’ worth of work, and the stated average bound is O((a+)^1.5 log n).Multithreaded recursive algorithms have near-perfect PRAM speedup, although thread-creation overhead outweighs it on very sparse matrices.Source: §3.3 · p. 9

• 4.33 bytes per cell is the reported k2-tree space use on very sparse Wikidata graph-database matrices.Source: §3.4 · p. 9
• On 80 synthetic 1,000 × 1,000 Boolean matrices, k2-trees were four times smaller, while plain sparse storage with Schoor’s algorithm was faster.Source: §3.4 · p. 9
• The comparison covered densities from 10^-4 to 10^-1 and used a baseline only slightly slower than GNU Octave as a sanity check.Source: §3.4 · p. 9

3.5 Kache-trees: cache-friendly 𝑘2-trees

• On real Web graphs, k2-trees are 0.85 the size of kache-trees; M×M⊤ did not finish in two cases because of memory limits.Source: Figure 2 · p. 10
• Depth-first deployment makes each k2-tree subtree contiguous, enabling sequential sums and contiguous copying of subtrees present in only one operand.The kache-tree stores internal-node signatures plus a last-internal-level bit rather than a separate parentheses sequence.Source: §3.5 · pp. 9–10
• On synthetic matrices, kache-trees use 12–18% more space and are up to 60% faster for sums and products of dense matrices.The reported cache-miss counts are 31%–42% higher for k2-trees on sums and up to 225% higher on products.Source: §3.5 · p. 10

3.6 Qdags and prejoining

• Qdags simulate each k2-tree as a virtual d-ary relation, enabling worst-case-optimal joins at 4.75 bytes per edge but with a 2^d intersection-time penalty.Source: §3.6 · p. 11
• Prejoining projects participating matrices onto fewer attributes before joining; storing two projections per relation raises space from 4.75 to 6.17 bytes per edge.The strategies preserve worst-case optimality, with speedups reaching three orders of magnitude on some query shapes.Source: §3.6 · p. 11
• A one-shot prejoin intersects A’s nonempty columns with B’s nonempty rows, then forms Cartesian products for each matching index; this runs Schoor’s algorithm directly on k2-trees.Source: §3.6 · p. 11
• 2–6× speedups for single products, 9–13× for three-matrix chains, up to 7× for four-matrix chains, and 2.5–7× on the full graph are reported for prejoining.Leapfrog is best on chains, while weak kernel is best on the large graph.Source: §3.6 · p. 11

3.7 Variants that exploit repetitions

• 2D block trees replace repeated submatrices with pointers, using 60%–80% of k2-tree space on Web graphs, but construction took 7,200 seconds versus 67 on eu-2005.Cell access ranged from 30% faster to three times slower; the described support covers cell and region access, not other operations.Source: §3.7 · pp. 11–12
• For 2D block trees, product algorithms can be adapted, but retaining O(a log n) time is unclear because traversals may yield no points.Source: §3.7 · p. 12
• Depth-first k2-tree variants share identical subtrees and improve compression, reaching 73% of the space on graph ID-2004; some multiply Boolean matrices faster, but not on every graph.The best-compressing shared-submatrix variant is the slowest, and the experiments concern matrix–matrix rather than matrix–vector products.Source: §3.7 · p. 12

3.8 Discussion

• The k2-tree line supports general algebra without decompression, trading fourfold space savings for slower operations; better layout can recover up to 60% speed at 18% more space.Source: §3.8 · p. 12
• Prejoining yields larger gains than most layout improvements, while repetition-aware variants remain slower than plain sparse CSR/CSC.Source: §3.8 · pp. 12–13

4.1 Origins

• Rows can be referenced through symmetric differences; this idea supports WebGraph’s windowed encoding and accelerates vector products by reusing a reference row’s result.A window limits candidates to previous rows, while an ordering that places similar rows nearby improves the references.Source: §4.1 · p. 13

4.2 Matrix–vector products on a referencing format

• For a referencing vector, each row stores its difference from an earlier reference, and its product is recovered by adding the reference row’s product to the residual product.The Boolean case uses residual entries +1 and −1; vertical slicing can improve matches in wide matrices, but increases the total size of compressed submatrices as the number of slices grows.Source: §4.2 · pp. 13–14

4.3 Differential compressed binary trees

• Differential compressed binary trees store row differences as trees, with leaf bits distinguishing insertions from deletions, and compute products by reusing reference-row results.The tree layout prunes empty column ranges; each row can be traversed to obtain its 1s.Source: §4.3 · p. 14

4.4 Matrix–matrix products

• Referencing also supports matrix–matrix products: referenced entries leave a sparse residual dot product, while CBM updates dense-embedding products along the reference forest.For Boolean products of referenced CBTs, simultaneous tree traversals can build the output directly as CBTs; experiments for static matrices are not reported.Source: §4.4 · p. 15

4.5 Experimental results

• On page graphs, residual A′ has 17%–26% of A’s nonzeros and yields 1.7×–2.6× speedups; CBT differences make time 17%–26% lower than WebGraph in Figure 4’s right-panel comparison.The Figure 4 panels use different codes and machines, so only within-panel comparisons are meaningful.Source: §4.5 · p. 15, Figure 4 · p. 16
• Against WebGraph, CBT versions were 2%–9% smaller and reduced time with differences by 17%–26%; reuse speedups over products without differences ranged 1.44×–3.22×, versus 1.36×–2.99× for WebGraph.Speedup follows the reduction in nonzeros. Figure 4 cautions that its panels use different codes and machines, so comparisons are meaningful only within each panel.Source: §4.5 · pp. 15–16, Figure 4 · p. 16

4.6 Finding the best references

• Choosing references is equivalent to finding a minimum spanning tree weighted by symmetric-difference sizes; its weight equals residual nonzeros, and product time is O(nnz(A′) + n).The exact MST is expensive to construct, so practical options include window-restricted greedy references, approximations, and an incremental exact method when MST edges are light.Source: §4.6 · pp. 16–17

4.7 Discussion

• Referencing works well when whole rows are similar, but construction may require good ordering or an expensive MST, and memory locality can limit speedup.Because it misses repeated value pairs separated by varying columns, the next section’s grammar approach addresses a different redundancy pattern.Source: §4.7 · p. 18

5.1 The CSRV representation

• CSRV linearizes nonzeros as value-index/column pairs plus row separators, so identical symbols denote the same value in the same column and support direct left and right products.The sequence length is nnz(A) + n.Source: §5.1 · p. 19, Figure 6 · p. 19

5.2 Grammar compression

• A straight-line grammar represents a sequence with rules that expand to that sequence; RePair heuristically replaces frequent adjacent pairs with nonterminals.Finding the smallest grammar is NP-hard, and RePair’s representation includes its rules and a final sequence.Source: §5.2 · p. 19

5.3 Products on the grammar

• Right and left products on the grammar take O(|C| + |R|) time and O(|R|) auxiliary words, using forward and backward passes over the rules.The left product requires processing rules in reverse order.Source: §5.3 · p. 20

5.4 Implementation and variants

• The implementation offers re_32, re_iv, and re_ans encodings that trade speed for compactness; row blocks enable parallel compression and products.More compact encodings reduce peak memory but not the number of operations, and are slower.Source: §5.4 · p. 21

5.5 Column reordering

• RePair benefits from adjacent repeated symbols, so column reordering groups correlated columns; the proposed similarity counts repeated nonzero pairs across columns.LKH, PathCover, PathCover+, and MWM are the four reordering algorithms described.Source: §5.5 · p. 21

5.6 Experimental results

• On the most compressible matrices, re_iv products are 3–12× faster than dense products; on the least compressible, they are slower, while two are about equal.For CLA comparisons, grammar formats use 3.1×–19.1× less peak memory and are at least twice as fast, with CLA’s compression time included and a Java-system caveat.Source: §5.6 · pp. 21–22, Figure 7 · p. 22, Figure 8 · p. 23
• Column reordering reduces size by up to 16% on Covtype and 10% on Airline78, but can increase time or memory on some matrices.RePair compression of 285–400-million-edge matrices takes 1.0–2.5 minutes with 16 threads; this comparison to Section 4 compression is not direct.Source: §5.6 · p. 22

5.7 Discussion and related work

• Grammar formats’ limitations include RePair’s O(|S|)-word compression space, backward-rule access for left products, and disappointing single-threaded performance on large matrices.The authors identify row permutations, co-clustering, semiring-annotated data, databases, and graphs as open directions.Source: §5.7 · p. 23

6.1 Idea and representation

• A biclique represents an all-ones submatrix through its row and column node sets, while uncovered edges remain in a residual graph.Extraction is heuristic because minimizing representation space is NP-hard; Hernández and Navarro’s procedure clusters similar adjacency lists and extracts bicliques from a prefix tree.Source: §6.1 · pp. 23–24
• Every n-vertex graph has a biclique partition of total size about 1/2 n²/log₂ n, and this bound is tight; these worst-case guarantees differ from the heuristics used on real graphs.The cited bounds imply Boolean matrix–vector multiplication in O(n²/log n) operations after decomposition.Source: §6.1 · p. 24

6.2 Products by a vector

• On it-2004, PageRank is 2.36× faster at a size ratio of 5.38; on transposed eu-2015-host, it is 1.92× faster at a ratio of 4.03.Biclique vertex totals can remove many edges: on it-2004, about 60 million vertices remove about 1,000 million edges.Source: Figure 10 · p. 26, §6.2 · p. 26
• The vector product processes each biclique as a shared sub-computation, with time proportional to the compressed graph size plus the output; exchanging row and column sets gives left products.A biclique-based product of Boolean matrices produces another biclique-based representation, so products can be chained.Source: §6.2 · p. 26, §6.3 · pp. 26–27

6.3 Boolean matrix–matrix products

• Boolean matrix products split into residual-by-residual, residual-by-bicliques, bicliques-by-residual, and bicliques-by-bicliques terms, yielding a compositional biclique representation.The result can be recompressed, but without recompression its bicliques may be less space-efficient than those extraction would find directly on the output.Source: §6.3 · p. 27

6.4 Experimental results for matrix–matrix products

• The k2-tree compresses inputs 20–28× on five graphs but is slower than the baseline in six of seven; bicliques compress 3–8× and give the largest speedups without recompression.The comparison covers seven graphs; the plotted speedup for A² is relative to the CSR implementation of Schoor’s algorithm.Source: Figure 12 · p. 29, §6.4 · p. 30
• With recompression, biclique outputs use 18%–38% of baseline space; without it, they use 20%–52% and are almost always faster than baseline, by up to 289×.The accelerator scenario is up to 34.3× faster even including extraction, but is slower on small matrices; without recompression, space degrades by 7%–40% in most cases.Source: §6.4 · pp. 29–30

6.5 Discussion

• Bicliques are relatively large and difficult to extract; the surveyed matrix–matrix algorithms are Boolean, and the survey identifies weighted and dynamic graphs, transitive closure, and parallel or GPU versions as future work.Individual cell access is also not efficient: locating a cell can require a worst-case O(|D|) search across bicliques.Source: §6.1 · p. 24, §6.5 · p. 30

7.1 Definition and products by a vector

• A sparse straight-line factorization represents A using sparse factors P, Q, T, and T′, with Q strictly lower triangular and size measured by their nonzeros.The factors encode shared fragments and residual entries; the identity factor, when used for P, is implicit.Source: §7.1 · pp. 30–31
• Both right and left vector products take O(s) arithmetic operations for a factorization of size s, using O(q + n + m) working words.Forward substitution computes Ax; the left product uses the transposed backward substitution over the same factor structure.Source: §7.1 · p. 31, Figure 13 · p. 32
• The compression ratio nnz(A)/s bounds the speedup expected from arithmetic alone, while factorization depth governs sequential steps and parallelism.Left and right products cost the same, avoiding storage of a transpose when both are needed; comparing families therefore concerns factorization quality and search cost.Source: §7.1 · pp. 31–32

7.2 The three families as instances

• Referencing, grammars, and bicliques instantiate the factorization differently: they share referenced rows, repeated consecutive sequences, and row-column sets, respectively.In the running example, the three factorizations have sizes 20, 22, and 22, each below nnz(A) = 27.Source: §7.2 · pp. 32–34
• The families differ in what structures they can share and how they find them: grammar and biclique searches are heuristic, while unrestricted referencing reduces to a minimum spanning tree problem.Bicliques can share non-adjacent rows and non-consecutive columns that a grammar rule cannot capture.Source: §7.2 · p. 34

7.3 Products of factorized matrices

• The factorization view does not cover k^2-trees or operations such as transitive closure, and the output size of factorized products is unbounded.For vector-only workloads, applying the two factors successively is typically cheaper than forming their matrix product; forming it can pay off when reused or needed explicitly.Source: §7.2 · p. 34, §7.3 · p. 36
• Multiplying two factorized matrices yields another factorization with q_A + q_B nodes, computed from sparse products between their factors.The resulting representation is valid but not necessarily small; it may need recompression, and its size has no general bound.Source: §7.3 · pp. 35–36

8.1 Cross-cutting observations

• Across vector products, speedup is a fraction of the reduction in symbols processed, while biclique matrix products achieve 34×–289× speedups against 3×–8× space reduction.Locality, decoding, pointer chasing, and rank operations can limit vector-product gains; cache-friendly kache-trees report up to 60% speedups with the same asymptotic work.Source: §8.1 · p. 37
• Format choice depends on matrix structure: Web graphs favor referencing, social networks can suit bicliques or k^2-trees, ML matrices with few distinct values suit grammars or CLA, and clustered Boolean relations suit k^2-trees.For matrices with little structure, such as Susy with over 98% nonzeros and over 20 million distinct values, dense or plain sparse storage is the appropriate choice.Source: §8.1 · p. 37

8.2 Which format when?

• The formats are static and can require preprocessing from microseconds per edge to hours, so they are intended for repeated operations rather than matrices used once or changed often.The survey’s practical recommendations include reference-based compression for repeatedly multiplied Web graphs and grammar compression for large ML matrices with few distinct values.Source: §8.1 · p. 37, §8.2 · p. 38

8.1 Cross-cutting observations

• The product of two factorizations may grow without a size bound, and skipping recompression can trade faster multiplication for larger output space.For biclique products, skipping recompression made products up to 20× faster at a 7%–40% space cost.Source: §8.1 · p. 38
• Auxiliary working space is nonzero, and algebraic operations can produce outputs much larger than their inputs.Grammar-based products need O(|R|) words, while referencing needs n partial results.Source: §8.1 · p. 38

8.3 Relation to theory

• Existing guarantees relate format size to different combinatorial measures, but there is no common measure of computation-friendly compressibility.Practical grammar compressors and biclique implementations approximate their respective optima heuristically.Source: §8.3 · pp. 38–39

9.1 Boolean and other algebras

• Biclique formats support Boolean matrix products and sums, but maintaining compression quality through composed operations remains open.Other pointwise operations, such as Hadamard products, may also be difficult; transitive closure is missing on the other surveyed formats.Source: §9.1 · p. 39
• Grammar formats extend to semirings, while referencing with deletions requires additive inverses and bicliques must partition edges over R.Compression ratios for these restricted forms and acceleration of semiring closures remain open questions.Source: §9.1 · p. 40

9.2 Compression and recompression

• Good references, grammars, and bicliques are expensive to construct; streaming or distributed construction and explicit space-time trade-offs remain largely unexplored.Dynamic support is also uneven: dynamic k^2-trees and evolving-graph differential trees exist, but whether product speedups survive updates is unexplored.Source: §9.2 · p. 40
• Valid factorizations of sums and products may not stay small, so recompression must control size across chains of operations.Possible directions include cheap recompression after each operation or formats that remain compact without extra work.Source: §9.2 · p. 40

9.3 Theory

• The minimum size and approximability of sparse straight-line factorizations, and which representations admit size-linear products, are open theoretical questions.Recompression theory could begin by characterizing factorizations irreducible by cheap exact steps and their distance from minimum size.Source: §9.3 · pp. 40–41

9.4 Applications

• Applications questions include combining lossy quantization with exact formats at scale and testing whether compressed methods suit modern neural-network weights.Set-difference compression has also been used to accelerate GNN training; semiring data and database workloads offer other potential settings.Source: §9.4 · p. 41
• Research prototypes need integration with sparse-algebra frameworks and a common benchmark suite to make formats comparable for practitioners.The surveyed papers use different datasets, hardware, and baselines.Source: §9.4 · p. 41

9.5 Computation models

• Locality and irregular memory access constrain computation models; cache-oblivious layouts, GPU performance, and distributed-memory partitioning remain concerns.A layered grammar implementation used 4–8× less device footprint than CSR on genotype matrices, with times within a small factor of cuSPARSE and lower energy.Source: §9.5 · p. 41

10 Conclusions

• The four surveyed families exploit spatial clustering, similar rows, repeated subsequences, or dense bipartite blocks.The k^2-tree family instead uses recursive partitioning and offers a complete Boolean algebra, with the least speedups over plain sparse representation.Source: §10 · p. 42
• Referencing, grammar, and biclique formats share sparse straight-line factorizations, whose forward and backward substitutions evaluate right and left products in time proportional to factor nonzeros.Products of factorizations remain factorizations, though their size is unbounded, making recompression a natural next step.Source: §10 · p. 42
• Reported speedups range from 2–3× on Web graphs with referencing to up to 34× for biclique Boolean matrix products, or 289× when the format is kept.Other reported results include grammar runtimes below dense products on the most compressible machine-learning matrices and 2–13× speedups for qdag product chains; space reductions range from modest to an order of magnitude.Source: §10 · p. 42
• Across the surveyed evaluations, speedups remain below compression ratios, preprocessing is costly, formats are static, and families have been tested in isolation.The survey identifies a common benchmark and framework as a valuable practice-oriented next step.Source: §10 · p. 42

A Formats that Require Decompression: A Brief Tour

• Decode-first formats range from whole-matrix decompression to on-the-fly decoding, and their operation time does not shrink with compressed size.The boundary is not sharp; some methods operate directly on compressed pieces and are treated in the main survey.Source: A Formats that Require Decompression:… · p. 48

A.1 General-purpose and floating-point compressors

• General-purpose compressors can have excellent compression ratios but ignore two-dimensional structure and require decoding the matrix or block before operations.In Ferragina et al.’s experiments, a multithreaded gzip-based product had the best memory footprint with grammar formats but was sometimes more than 40× slower.Source: §A.1 · p. 48
• Floating-point compressors such as fpzip, Gorilla, and ZFP reduce memory or disk use, but decode blocks before arithmetic.ZFP’s fixed-rate mode permits random access to blocks.Source: §A.1 · p. 48

A.2 Index and value coding for sparse formats

• Compressed sparse index formats decode indices inside multiplication, so work remains proportional to nnz(A), with gains chiefly from bandwidth.GPU dtANS compression reaches up to 11.77× smaller than the smallest cuSPARSE format and a best speedup of 3.48× on matrices with at least 225 nonzeros.Source: §A.2 · p. 49
• Integer-sequence and gap codes decode data before use and can further encode residual graphs or grammar sequences, at the cost of decoding.They are orthogonal to and combinable with computation-friendly formats.Source: §A.2 · p. 49

A.3 Blocked and structured formats

• Blocked and GPU-oriented sparse formats trade index savings or hardware regularity against stored padding, with work proportional to stored entries.The k^2-tree family is described as a hierarchical, more principled version of blocking.Source: §A.3 · p. 49

A.4 Lightweight schemes from column stores, and CLA

• Column-store methods and Compressed Linear Algebra can support products directly on compressed columns, while more complex schemes may require partial decoding.CLA groups correlated columns and has a cost related to distinct values and runs.Source: §A.4 · p. 49

A.5 Lossy compression for machine learning

• Lossy deep-learning compression can affect accuracy in data- and model-dependent ways, while lossy and lossless techniques can be combined sequentially.Applying lossless compression after lossy compression is the setting in which the survey’s formats remain exact.Source: §A.5 · p. 50