はじめに 機械学習エンジニアの本田志温です。最近担当した類似アイテム推薦の案件で、BigQueryを使って最大内積検索(MIPS; maximum inner-product search)1 を実装したので、その方法と高速化のテクニックを紹介します。 類似アイテム推薦は「多数のアイテム候補から、クエリとなるアイテムに最も類似したK件を抽出する」というタスクなので、MIPSないし近傍探索の枠組みで解くことが一般的です。 一定の規模を持つサービスでMIPSを実装しようとすると、アイテム数×特徴量次元の行列が何かと厄介です2。第一に、MIPSを素朴な行列積で実装すると、時間・空間計算量がアイテム数の2乗でかかってきます。典型的には空間計算量の方がボトルネックになりやすく、RAMの制約に収めるための工夫が必要になるでしょう。第二に、アイテム数が膨大な場合、特徴量マートから全アイテムの特徴量を転送