Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 ยท Collaborative Filtering

Scaling Neighborhood Methods

Make neighborhood recommenders fast: sparse matrices, keeping only the top-k neighbors per item, precomputed lists, batching and approximate nearest neighbors, with timings.

A neighborhood model that works on 100 items falls over at 10 million. The full item-item matrix has nยฒ entries: a million items would need a trillion numbers. This lesson covers the standard tricks to keep memory and latency under control: sparsity, top-k pruning, precomputation, batching and approximate nearest neighbors, and closes the chapter with a comparison of the collaborative methods you have built.

You already have the models: user-based, item-based and implicit item-kNN. Here we make them cheap.

Where the cost comes from

  • Similarity computation: O(n_itemsยฒ ยท avg_overlap), done offline.
  • Storage: a dense n ร— n float matrix. 100,000 items x 100,000 x 4 bytes = 40 GB.
  • Serving: scoring all candidates for a user against their whole history.

The way out is to realize that most pairs are useless. Only the strongest neighbors of each item influence recommendations, and most item pairs never co-occur at all.

Step 1: stay sparse

Co-occurrence between items only exists where at least one user touched both. Xแต€ X computed as a sparse product never creates the empty cells, and most of the matrix stays empty.

Python Sparse co-occurrence is mostly empty

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 2: keep only the top-k neighbors

For each item keep the k highest similarities (say 50) and drop the rest. Memory becomes n_items ร— k, linear in the catalog. Prediction is dominated by the strongest neighbors anyway, so most of the quality survives while storage drops sharply. The size of the loss is something you must measure, as below.

Python Top-k pruning: memory and agreement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On this small catalog of 300 items, keeping 5 neighbors per item changes about half of each top-10 list, 20 neighbors keep about 71% of it and 50 keep about 81%. The loss is real on a tiny catalog; with millions of items and a validation metric (HitRate or NDCG) the picture is usually much kinder. Pick the smallest k whose validation metric is within noise of the full model.

Step 3: precompute and cache

Item similarities change slowly, so compute the top-k neighbor lists in a nightly batch job and store them in a key-value store (Redis, a database table). At request time:

  1. Fetch the user's recent history (a few dozen items).
  2. For each history item, fetch its neighbor list.
  3. Sum scores in a dictionary, drop seen items, return the top N.

This costs O(history ร— k) per request, independent of catalog size.

Python Serving from precomputed neighbor lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 4: batch and vectorize

Compute similarities in blocks (a few thousand items at a time) so that you never hold more than a block of the dense result, apply top-k pruning to each block, then move on. Use sparse matrix products, never Python loops over pairs. For user-based CF, the same idea works on user blocks, though the number of users usually makes it the more expensive choice.

Step 5: approximate nearest neighbors

When item vectors are dense embeddings (from SVD or neural models), exact top-k over millions of items is slow. Approximate nearest neighbor (ANN) libraries (FAISS, ScaNN, HNSW graphs in Annoy or hnswlib) return the near-best neighbors in milliseconds by trading a little recall. You measure the trade-off as recall@k against the exact answer. These libraries cannot be installed in the browser runner, so here is the core idea in plain NumPy: partition vectors into buckets with random hyperplanes (locality-sensitive hashing) and search only the matching bucket.

Python Random-hyperplane hashing in miniature

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

More tables scan more candidates and raise recall (from 30% with one table to 50% with twelve here, while still reading under 2% of the vectors): the speed-versus-accuracy dial that every ANN index exposes. Real indexes use smarter structures and reach much higher recall.

Choosing a collaborative method

Situation Reasonable choice
Few thousand users, explicit ratings, explanations needed user-based CF with shrinkage
Many users, stable catalog item-based CF with top-k lists in a cache
Clicks and purchases only implicit item-kNN with popularity normalization
Huge scale, dense embeddings ANN over learned vectors (see matrix factorization)
Brand-new items or users content-based or popularity fallback until data arrives

Scaling recipe

Stay sparse Never build the dense matrix
Top-k only 50 neighbors per item
Precompute Nightly batch, cache lists
Block it Process items in chunks

Serving cost: history ร— k, not catalog size.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does keeping only the top-k neighbors per item preserve most of the quality?

    Predictions are dominated by the most similar items, so dropping weak links changes lists less than their number suggests; measure the loss on validation data.
  2. 2. What is the per-request cost when serving from precomputed neighbor lists?

    You look up one neighbor list per history item and merge them.
  3. 3. What does recall@k measure for an ANN index?

    It compares the approximate results to the exact top k.
  4. 4. Which scaling step avoids ever materializing the dense n by n matrix?

    Block-wise sparse products plus pruning keep only the small set of useful similarities.

Summary

  • The dense item-item matrix is the bottleneck; keep products sparse and keep only top-k neighbors per item.
  • Precompute neighbor lists offline and serve by merging a handful of lookups.
  • Process in blocks; use ANN indexes for dense embeddings and tune them with recall@k.
  • Choose the collaborative method by data type, scale and the need for explanations.

Next: Latent Factors and SVD for Recommendations