Co-occurrence Matrices › Efficient Construction Algorithms

Building a co-occurrence matrix from a large corpus requires careful design. A naive approach, iterating over all token pairs within windows, is $O(N \cdot k)$ for a corpus of $N$ tokens and window size $k$. That is manageable for modest corpora, but large corpora require attention to memory and parallelism.

The standard approach streams through the corpus one sentence at a time, maintaining a sliding window. For each token in the window, we emit a (target, context) pair and increment the corresponding matrix entry. Using a hash map to accumulate counts requires $O(1)$ amortized per update and avoids allocating a full $V \times V$ matrix.

The key insight in streaming construction is that you never need to hold the entire corpus in memory. You process it one sentence at a time, update the count map, and discard the sentence. The count map grows only as large as the number of distinct word pairs observed, which for realistic corpora is much smaller than $V^2$.

After processing the corpus, the hash map is converted to CSR format for efficient numerical operations. The construction cost is $O(N \cdot k)$ time and $O(|\text{nonzeros}|)$ space, where $|\text{nonzeros}|$ is the number of distinct co-occurrence pairs observed. For large corpora, this is typically in the hundreds of millions of pairs: far smaller than $V^2$ but large enough to require careful memory management.

Before building the matrix, you need a fixed vocabulary. Common practice is a two-pass approach:

1. First pass: Count all word frequencies, discard words below a minimum frequency threshold (typically 5-10 occurrences).
2. Second pass: Build the co-occurrence matrix using only the retained vocabulary.

Low-frequency words are discarded because their co-occurrence statistics are unreliable: a word appearing twice in the corpus will have co-occurrence counts that are essentially noise. Discarding rare words also dramatically reduces vocabulary size and matrix density.

The frequency threshold is a hyperparameter that trades off vocabulary coverage for statistical reliability. A lower threshold keeps more words but introduces more noisy rows into the matrix. A higher threshold keeps only well-attested words but excludes rare technical terms, proper nouns, and neologisms. For large corpora, a threshold of 5-20 is typical; for small corpora, even a threshold of 2 may be appropriate to preserve enough words for meaningful analysis.

For very large corpora, the construction can be parallelized by partitioning the corpus into chunks and processing each chunk independently. Each worker produces a partial co-occurrence map; these maps are merged at the end by summing counts for shared pairs. This scales linearly with the number of workers, making it possible to build co-occurrence matrices from billions of tokens in a matter of hours.

GloVe's original implementation (Pennington et al., 2014) uses this approach with multiple threads and efficient binary file formats to build co-occurrence counts from Wikipedia-scale corpora (billions of tokens) in hours rather than days. The implementation writes partial counts to disk in COO format, then merges and sorts them before converting to the final matrix representation. This external memory sorting approach allows corpora far larger than available RAM to be processed efficiently.

For the biggest corpora, such as C4 (750 GB of text) or the Pile (800 GB), even this approach requires careful engineering. Modern practice typically uses distributed computing frameworks (Spark, Dask) to partition the corpus across many machines, each building a local co-occurrence map, with a final reduce step that sums counts across partitions.