Compressed Sparse Row (CSR)

Definition #

CSR (Compressed Sparse Row) is a storage format used to efficiently store a sparse matrix.

Its role in our system is:

Graph ↓ Adjacency Matrix ↓ Mostly 0s ↓ Sparse Matrix ↓ CSR ↓ Efficient storage/querying

It avoids physically storing all those zeros.

The Problem That Led to It #

Our adjacency matrix might look like:

  A B C D

A 0 1 1 0 B 1 0 0 0 C 1 0 0 1 D 0 0 1 0

There are 16 positions, but only 6 meaningful connections.

For a billion-node network, storing every possible position would be impractical.

What Problem It Solves #

CSR stores only the non-zero values, while also storing enough information to know where those values belong.

Conceptually:

Matrix ↓ Find non-zeros ↓ Store values + their positions ↓ CSR

So we don't store the huge collection of zeros.

What Happens If Not Used #

We would have to store and process enormous numbers of unnecessary zero entries, wasting memory and making operations much harder to scale.

Easy Wording #

CSR is a way of storing only the useful parts of a sparse matrix while remembering where those parts belong.

Layman Example #

Imagine a warehouse with 1 million shelves, but only 10,000 shelves contain products.

Instead of recording every empty shelf, CSR records:

“These 10,000 shelves contain something, and here's where each one is.”

Technical Example #

CSR uses three main arrays:

data indices indptr

For our example, these work together to answer:

What values exist, and where do they belong?

We'll unpack these three arrays one at a time next, because understanding them is the key to actually understanding CSR rather than memorizing it.

Limitation #

CSR is designed for sparse matrices. If a matrix is dense, there aren't many zeros to eliminate, so CSR's extra indexing structure may not provide an advantage.