compressed sparse row representation

[[concept]]

Compressed Sparse Row (CSR) representation

$A\in {\mathbb{R}}^{n\times m}$ can become a set of 3 tensors/“lists”. We get this representation by realizing that we can encode the row index in the COO representation a bit more efficiently.

Instead of writing out the row index for each element, we can collect the column indices for each row, put each of these collections together, and then have a pointer tell us where to start reading.

If $A$ has $z$ non-zero entries, then

• the column tensor contains $z$ entries. Each entry contains the column index for one of the non-zero elements, sorted by ascending row index.
• row or pointer tensor contains $n+1$ entries
  • the first $n$ entries contain the starting index for where the row’s elements start in the column tensor
  • the last entry is $z$
• value tensor contains $z$ entries and contains the non-zero elements sorted by row then column index.

Example

12 & 0 & 26 & 0 \\ 0 & 0 & 19 & 14 \\ 26 & 19 & 0 & 0 \\ 0 & 14 & 0 & 7 \end{bmatrix}$$ `Pointer = [0 2 4 6]` $$\begin{array}{c|cccc} \text{index} & 0 & 1 & 2 & 3 \\ \hline \text{read start} &0 & 2 & 4 & 6 \end{array}$$ `Column = [0 2 2 3 0 1 1 3]` $$\begin{array}{c|cc|cc|cc|cc} \text{index} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \text{col indx} &0 & 2 & 2 & 3 & 0 & 1 & 1 & 3 \end{array}$$ `Value = [12 16 19 14 26 19 14 7]` $$\begin{array}{c|cc|cc|cc|cc} \text{index} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \text{value} & 12 & 26 & 19 & 14 & 26 & 19 & 14 & 7 \end{array}$$

---

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source