Amazon の Item-to-Item CF の論文を読んだメモ協調フィルタリングの詳細については こちらの資料 に譲るとして、端的にいうと「協調フィルタリング」というのは、アクティブユーザ（推薦対象のユーザ）に類似する他のユーザを、商品購入履歴や評点情報の近さから探し出し、そのユーザが購入している商品をアクティブユーザに推薦する、というものです。 古典的な GroupLens のユーザベース協調フィルタリングでは、時間計算量の制約から、オンラインでの推薦を提供できるのは中規模（数十万ユーザ、数万点の商品程度？）のデータセットまでとなっているようです。このユーザベースの協調フィルタリングの時間計算量は、ユーザ数を m、商品数を n とすると、最悪のケースで O(mn) となります。ただし、実際のデータセットにおいては、ユーザと商品の関係が疎であることが多いので、その場合には O(m + n) の時間計算量に近くなるそうです。どちらにせよ、Amazon
