Sparse Arrays
A sparse array stores only the entries that are actually set, treating every absent index as an implicit zero. When most of a range is empty, this turns memory from proportional to the index range into proportional to the real data.
Paying for Emptiness
A sparse array or sparse matrix is one in which the overwhelming majority of entries are zero — or whatever the structure's default value is. Storing them densely means allocating memory for every position, and when 99% of those positions hold nothing, 99% of the memory is spent recording absence.
The scale of the waste becomes clear with real numbers. A 100,000 × 100,000 matrix of 8-byte doubles requires 80 gigabytes dense. If only 0.01% of its entries are non-zero — a million values — the actual data is 8 megabytes. The dense representation costs ten thousand times more than the information it holds.
Time is wasted alongside memory. Multiplying two dense matrices is O(n³) regardless of content, so a dense algorithm spends nearly all its arithmetic multiplying zeros and adding the results to running totals. A sparse algorithm touches only the entries that exist, and its cost scales with the number of non-zeros rather than with the dimensions.
So a sparse format stores only the non-zero entries, along with enough index information to know where each one belongs. That index overhead is the price: each stored value now carries its coordinates, so a sparse format is larger than dense when the matrix is not actually sparse.
The crossover is worth having a number for. A format storing a value plus one or two indices costs roughly two to three times as much per entry as a dense slot, so sparse representations start winning once the density falls below about one third, and win overwhelmingly below 10%. Above that, dense storage is both smaller and faster, because contiguous memory and predictable access beat index lookups.
- Dense storage allocates memory for every absent value
- Sparse cost scales with the non-zero count, not the dimensions
- Each stored entry carries index overhead alongside its value
- Below ~10% density sparse wins; above ~33% dense is better
Coordinate List and Dictionary of Keys
COO — coordinate list — is the simplest format and the easiest to reason about. Each non-zero entry is stored as a triple of (row, column, value), held in three parallel arrays or one array of records.
Its virtues are directness and cheap construction. Appending a new entry is O(1) and requires no reorganisation, so COO is the natural format for building a matrix incrementally or for reading one from a file.
Its weakness is lookup. Finding the value at a specific position means scanning the triples, at O(nnz) where nnz is the number of non-zeros. Sorting the entries by row then column improves this to O(log nnz) via binary search, but sorted order must then be maintained on every insertion.
COO is also the standard interchange format, which is why the Matrix Market file format is essentially a list of triples and why libraries accept it as input before converting internally.
DOK — dictionary of keys — stores a hash map from (row, column) to value. Lookup, insertion and deletion are all O(1) average, which makes it the best format for a matrix that is still being modified, particularly with unpredictable access patterns.
The costs are hashing overhead per access, memory for the hash table's own structure, and the loss of any ordering — iterating a DOK visits entries in an arbitrary sequence, which makes it poor for the sequential arithmetic that matrix algorithms perform.
The practical workflow that follows from all this is a two-phase one: build in COO or DOK, then convert to CSR for computation. SciPy's documentation recommends exactly this, and it is why scipy.sparse provides several formats rather than one.
- COO stores (row, column, value) triples — O(1) append, O(nnz) lookup
- It is the standard format for construction and file interchange
- DOK hashes the coordinate pair for O(1) access, but loses ordering
- Build in COO or DOK, then convert to CSR to compute
Compressed Sparse Row
CSR is the format that serious numerical work uses, and understanding its three arrays is the substance of this topic.
It stores the non-zeros row by row, left to right, in two arrays of length nnz: values holds the entries themselves and colIndices holds the column of each. The third array, rowPointers, has length rows + 1 and holds, for each row, the index in the other two arrays where that row's entries begin.
The compression is in that third array. COO stores a row number for every entry; CSR stores one pointer per row, exploiting the fact that entries are grouped. For a matrix with far more non-zeros than rows, this is a substantial saving.
The consequences follow directly from the layout. Row r's entries are exactly the slice from rowPointers[r] to rowPointers[r+1], retrievable in O(1) plus the length of the row. The number of non-zeros in row r is the difference of those two pointers, computable in O(1). And the final entry of rowPointers is nnz itself, which is why it has one extra slot — the same sentinel trick that removes a special case at the end.
Looking up a single element requires searching within the row's slice, at O(log k) with binary search over the sorted column indices, or O(k) linearly. So CSR is not the format for random single-element access.
What it is for is matrix-vector multiplication, the operation that dominates iterative solvers. Each output element is the dot product of one row with the vector, and CSR delivers each row contiguously — so the loop reads memory sequentially and touches only real entries. This is why CSR backs the solvers in nearly every scientific computing library.
CSC — compressed sparse column — is the identical scheme transposed, compressing the column index instead. It makes column slicing fast and suits algorithms that work column-wise, including many linear solvers and MATLAB's internal representation.
| Format | Stores | Fast at | Weak at |
|---|---|---|---|
| COO | (row, col, value) triples | Appending, file I/O | Lookup — O(nnz) |
| DOK | Hash from (row, col) | Random access, edits | Iteration order, overhead |
| CSR | values, colIndices, rowPointers | Row slicing, matrix-vector | Single-element lookup, edits |
| CSC | Column-compressed equivalent | Column slicing | Row operations |
- Three arrays: values, column indices, and one pointer per row
- Row r spans
rowPointers[r]torowPointers[r+1]— O(1) to locate - Built for matrix-vector products, which read each row contiguously
- Poor for modification — inserting shifts everything after it
Terms, operations, and practical uses
Memory concepts
- SparsityThe ratio of zero (or default) elements to total elements in a dataset. High sparsity means most data is empty.
- Default ValueThe value assumed for any index that is not explicitly stored in the sparse representation (usually 0 or null).
- OverheadThe extra memory required to store indices or keys. If a dataset isn't sparse enough, storing keys wastes more memory than a dense array.
Representations
- Hash Map / DictionaryUsing the array index as a key. O(1) expected lookup, but has significant memory overhead per entry.
- Coordinate List (COO)Storing a simple list of (index, value) tuples. Very compact, but requires O(N) or O(log N) search to find a specific index.
- Compressed Sparse Row (CSR)A highly optimized format for 2D sparse matrices using three 1D arrays, enabling extremely fast matrix multiplication.
Applications
- Adjacency MatricesRepresenting graphs. Social networks have billions of nodes but few connections per node, making dense matrices impossible.
- Machine LearningTraining models on sparse features like one-hot encoded text data, where 99% of feature columns are zero.
- Scientific ComputingSolving massive systems of linear equations (finite element analysis) where only local elements interact.
Sparse Array using Coordinate List (COO)
coo = []
coo.append((100, 5))
coo.append((999, 2))
coo.append((50, 9))
# Sort by index for binary search capabilities
coo.sort(key=lambda x: x[0])
print('Sorted COO:', coo)#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<pair<int, int>> coo;
coo.push_back({100, 5});
coo.push_back({999, 2});
coo.push_back({50, 9});
sort(coo.begin(), coo.end());
cout << "Sorted COO: [";
for(size_t i = 0; i < coo.size(); i++) {
if (i) cout << ", ";
cout << '(' << coo[i].first << ", " << coo[i].second << ')';
}
cout << "]\n";
}import java.util.*;
class Main {
static class Element implements Comparable<Element> {
int index, value;
Element(int i, int v) {
index = i;
value = v;
}
public int compareTo(Element other) {
return this.index - other.index;
}
}
public static void main(String[] args) {
List<Element> coo = new ArrayList<>();
coo.add(new Element(100, 5));
coo.add(new Element(999, 2));
coo.add(new Element(50, 9));
Collections.sort(coo);
StringBuilder sb = new StringBuilder("Sorted COO: [");
for (int i = 0; i < coo.size(); i++) {
if (i > 0) sb.append(", ");
sb.append('(').append(coo.get(i).index).append(", ").append(coo.get(i).value).append(')');
}
System.out.println(sb.append("]"));
}
}Step through it
Running on Set index 100 to 5, index 999 to 2, index 50 to 9
Read all 11 Steps
- The dense array wastes memory A logical array spanning index 0 to 999 with only three non-zero entries still allocates 1000 slots. At 4 bytes each that is 4 KB to store 12 bytes of real data — 99.7% of it zeros.
- Store coordinates instead of slots Coordinate list (COO) format keeps one (index, value) pair per non-zero entry and nothing else. Memory becomes proportional to the number of non-zeros, not to the index range.
- Insert (100, 5) Append the first pair. Index 100 holds 5; every index not present in the list is implicitly zero, which is the defining convention of a sparse structure.
- Insert (999, 2) Append the second pair. Note the index jumps from 100 to 999 at no storage cost — the 898 zeros between them are never materialised.
- Insert (50, 9) Append the third pair. Insertion order is arbitrary, so the list is now out of order: 100, 999, 50.
- Unsorted lookup costs O(n) To read index 100 right now you must scan every pair, because nothing constrains where it sits. With a million non-zeros that is a million comparisons per read.
- Sort by index Sorting once by index makes the list monotonic, which is the precondition binary search needs. One O(n log n) sort buys O(log n) on every subsequent read.
- Look up index 100: mid = 1 Binary search over the keys. mid is 1, whose key is 100 — an exact match on the first probe.
- Return the value 5 The pair at index 1 is (100, 5), so the logical array's element 100 is 5. Three stored pairs answered a query over a 1000-element range.
- A miss returns the implicit zero Searching for index 300 probes 100, then 999, then runs out of interval without a match. Absence is not an error here — it means the entry was never stored, so the correct answer is 0.
- When sparse beats dense COO wins when non-zeros are a small fraction of the range. Store a pair as two 4-byte ints and the break-even is roughly 50% density; below that sparse saves memory, above it the index overhead makes a plain array cheaper and faster.
Where Sparsity Actually Arises
Sparse structures matter because sparse data is the normal case in several large domains, not an exception.
Graphs. An adjacency matrix for a graph with V vertices has V² entries, but a real graph has far fewer edges than that. A road network's junctions connect to a handful of roads each; a social network's users follow hundreds out of millions. This is precisely why an adjacency list is the default graph representation — it is a sparse format, and choosing a dense matrix instead turns an O(V + E) traversal into O(V²).
Recommendation systems. A user-item matrix of ratings is extraordinarily sparse: each user has rated a vanishing fraction of the catalogue. Netflix's published dataset was around 1% filled. Collaborative filtering is essentially the study of how to work with such a matrix.
Text processing. A document-term matrix has a column per vocabulary word, and any single document uses a tiny subset. This is why scikit-learn's vectorisers return sparse matrices by default rather than dense ones.
Scientific computing. Discretising a differential equation over a mesh produces a matrix where each point couples only to its immediate neighbours, so each row has a handful of non-zeros out of millions of columns. Finite element and finite difference methods generate these routinely, and iterative solvers exist precisely because the matrices are too large to store or factorise densely.
A related idea shares the name but not the mechanism: a sparse table is a precomputed structure answering range minimum queries in O(1) after O(n log n) preprocessing. It is unrelated to sparse storage, and the name collision is worth knowing so the two are not confused in a question.
The decision rule, stated plainly: estimate the density first. Below roughly 10% non-zero, a sparse format saves substantial memory and time. Above roughly a third, dense storage is faster and simpler despite the wasted space. In between, measure — the constant factors and the access pattern decide, not the asymptotics.
- Adjacency lists are a sparse format, which is why they beat matrices
- Recommendation and document-term matrices are ~1% filled
- Finite element meshes couple each point only to its neighbours
- A sparse table is an unrelated range-query structure, despite the name