エンジニアの谷田です。 最大内積探索問題(Maximum Inner Product Search, 以下MIPS)ってご存知でしょうか?データベースに登録された多くのアイテムのベクトルのうち、クエリのベクトルとの内積を最大化するアイテムを探す問題です。行列分解を用いてユーザにアイテムをレコメンドするときなど、この探索が問題になってくることがあります。 MIPSを解く単純な方法は、与えられたクエリに対してデータベースのすべてのアイテムとの内積を計算することですが、これにはアイテム数に比例した時間がかかります。そのため、アイテムが何千万や何億といった数にのぼると、ベストなアイテムを返す処理を遅延なくリアルタイムで行うのは厳しくなってしまいます。 これを解決するために、局所性鋭敏型ハッシュ(Locality Sensitive Hashing, 以下LSH)という手法をもとにしたアルゴリズムが