Dimensionality reduction is crucial for handling high-dimensional text data like bag-of-words vectors, but traditional methods hit a wall with memory constraints. The Johnson-Lindenstrauss lemma promises low-distortion projections via random matrix multiplication, yet storing gigantic matrices for billion-word vocabularies becomes impractical. A breakthrough hashing trick eliminates this bottleneck entirely—replacing explicit matrices with deterministic bitwise operations.

The Core Insight: Hashing as Randomness

Instead of storing a massive projection matrix (with entries of ±1), we exploit the properties of hash functions. Each word's hash serves as a seed for generating pseudo-random values equivalent to matrix entries. By applying bitwise rotations and mixing functions (like rotl and mix32), we dynamically compute the "matrix" coefficients during processing:

uint32_t row_hash = mix32(rotl32(outp_hash, row));
if (row_hash % 2 == 0) { res_o[row]++; } 
else { res_o[row]--; }

Zero-Memory Text Featurization

Crucially, this approach avoids materializing both the input vectors and the projection matrix. The algorithm streams tokens directly, accumulating projections in a single pass:
- Ngram handling: Captures context via sliding windows while packing tokens into 64-bit integers.
- On-the-fly hashing: Uses mix64to32 to convert ngrams to uniform hashes.
- Parallel projections: Generates multiple independent dimensions simultaneously via rotl offsets.
- L1 normalization: Ensures scale-invariant embeddings post-processing.

Performance and Implications

Benchmarked on a 2018 ThinkPad, this technique embedded 665,000 documents in 12.3 seconds—dramatically outpacing conventional methods. The implications are profound:
1. Memory efficiency*: Eliminates O(vocabulary_size × dimensions) storage, critical for edge devices. 2. *Real-time applications: Enables on-device NLP for chatbots or search engines.
3. Scalability: Extends to billion-scale datasets without infrastructure overhaul.

As large language models dominate headlines, this hashing trick offers a counterpoint: sometimes, elegant bit manipulation outperforms brute-force parameter counts. For developers working with high-cardinality data, it’s a reminder that clever algorithms can turn hardware limitations into opportunities.

Source: One Weird Hashing Trick (Hella Cheap Notes)