Sparse Matrix Representations

Also Known As

TL;DR

Explanation

Dense 2D array: O(m*n) space — wasteful when <1% of values are non-zero. COO (Coordinate): store (row, col, value) triples for each non-zero — simple to build. CSR (Compressed Sparse Row): three arrays — fast row iteration and matrix-vector products. DOK (Dictionary of Keys): hash map of (row,col)→value — fast element access. Applications: recommendation systems (user×item ratings), graph adjacency, NLP term-document matrices. 1M users × 100K products densely requires 400GB — as CSR at 1% density, 4GB.

Common Misconception

Why It Matters

Common Mistakes

• Dense matrix for sparse data — memory infeasible
• Wrong format for the operation — COO for building, CSR for computation
• Not checking sparsity before choosing format
• Building CSR directly instead of building COO then converting

Code Examples

// Dense matrix for user-item ratings — physically impossible:
$ratings = array_fill(0, 1000000, array_fill(0, 100000, 0.0));
// 1M * 100K * 8 bytes = 800TB — impossible

// DOK: only store non-zero ratings:
$ratings = [];
$ratings["42:1337"] = 4.5; // User 42 rated item 1337: 4.5 stars
// 1M users * 200 ratings avg = 200M entries
// Memory: 200M * ~30 bytes = 6GB — feasible

References

• ↗ https://en.wikipedia.org/wiki/Sparse_matrix

Tags

Related Terms