Real architecture · Mid
Amazon item-to-item CF
Real production architecture. Key points: item-item similarity and offline precomputation.
Short answer
Real production architecture. Key points: item-item similarity and offline precomputation. This case starts from a paper in which Amazon engineers describe the recommendation algorithm they call item-to-item collaborative filtering. The environment they describe is harsh: a large store can have tens of millions of customers and millions of distinct items in the catalog, and the paper places Amazon itself at…
01 · CONTEXT
The problem: recommending fast for millions
This case starts from a paper in which Amazon engineers describe the recommendation algorithm they call item-to-item collaborative filtering. The environment they describe is harsh: a large store can have tens of millions of customers and millions of distinct items in the catalog, and the paper places Amazon itself at more than 29 million customers.
Beyond scale, there are product requirements. Many applications require the result in real time, within half a second at most, without giving up quality. New customers have very little information, longtime customers can have thousands of purchases and ratings, and each interaction generates new data to which the algorithm must react immediately.
Recommendations appear in email campaigns and on site pages, including the shopping cart, where suggestions start from the items the person has already put there.
02 · ALTERNATIVES
Why the common approaches were not enough
The paper compares three common approaches with the authors' proposal. The first, traditional collaborative filtering, represents each customer as a vector of items and looks for the customers most similar to the person.
The person asks for recommendations and the service needs to decide what to show at that moment.
In the traditional version, the online part grows with the number of customers and items in the catalog.
With very large sets of customers and items, this online work causes serious performance and scale problems.
Reducing the data, by sampling, partitioning, or dimensionality reduction, eases the cost, but the authors themselves say that all these methods also reduce the quality of the recommendations.
| Offline and online work | Quality according to the paper | |
|---|---|---|
| Traditional collaborative | Little or no offline computation; the online part grows with customers and items. | Reducing the data to scale also reduces quality. |
| Cluster models | Can do much of the work offline. | The quality of the recommendations is relatively poor. |
| Search-based | Build keyword, category, and author indexes offline. | Fail to deliver interesting, targeted titles. |
| Item-to-item | Builds the expensive similar-items table offline. | According to the authors, the quality is excellent because it recommends highly correlated items. |
03 · OFFLINE
The similar-items table
The central idea flips the question. Instead of finding customers similar to the person, the algorithm matches each purchased or rated item to similar items and combines those similar items into a recommendation list.
To do this, it builds a table of similar items, looking for items that customers tend to buy together. The expensive table is created offline, before the requests.
In architectural terms, this is equivalent to a batch data pipeline job: it reads the purchase history and writes a result ready for lookup.
The starting point is the history of who bought what.
For each item, the job walks through the customers who bought it and the other items those customers bought, avoiding comparing pairs of products with no customer in common.
Then it computes the similarity between the item and the related ones; a common method is cosine, with one vector per item whose dimensions are the customers who bought it.
The result goes into a similar-items table, ready to be queried later.
This offline computation is very time-consuming, but, according to the authors, sampling the customers who buy best-sellers reduces the run time even further with little loss of quality.
04 · ONLINE
Answering the request without recomputing
On the online path there is no search for similar customers. The algorithm takes the person's items, looks up each one's similar items in the table, aggregates, and recommends the most popular or correlated ones.
The person opens a page or the cart and the service receives the request.
The service reads the items the person bought or rated, and this number defines the cost of the online computation.
For each of these items, the service queries the precomputed similar-items table.
The similar items are aggregated and the service returns the most popular or correlated ones.
The cost of this step depends only on how many items the person bought or rated, and the online part scales independently of the catalog size and the total number of customers. That is why, the authors say, the algorithm is fast even on extremely large sets.
05 · LESSONS
What to take into the interview
In conclusion, the authors list what a good recommendation algorithm needs: scale over huge customer bases and catalogs, generate recommendations online in subsecond time, and react immediately to changes in user data.
In an interview, it is worth using the same reasoning: separate what changes on every request from what can be precomputed, and say what the variable input of the online path is. It is also worth asking what staleness is acceptable for the precomputed table.
Frequently asked questions
What is Amazon item-to-item CF?
Real production architecture. Key points: item-item similarity and offline precomputation.
What does the Amazon item-to-item CF design cover?
It is organized in these sections: The problem: recommending fast for millions, Why the common approaches were not enough, The similar-items table, Answering the request without recomputing, and What to take into the interview.
How long is Amazon item-to-item CF and what level is it?
It takes about 15 minutes to read and is rated Mid level.
Now design it yourself
Run this case as an interview in the System Design school: you make the decisions, the tutor challenges them and you see how your design scores.