ベクトル検索高速化手法の一つ、IVFを理解する

IVF(Inverted File)とは

結論

ベクトル検索を高速化するための手法の一つ

概要フロー

1. データをK-meansでクラスタ分け
2. 入力に対して、各クラスタのセントロイドに対して類似度検索
3. 最も類似度の高いクラスタの中で全数検索することで、高速なベクトル検索が可能になる

こんな感じっぽい。

例

例えば
800万品種の生物情報が保存されたデータベースがあり
あなたは撮影した生物の品種をこのデータベースから検索する　としよう

だが800万品種の生物データベースから撮影した生物を比較して、
探し当てるのはとても疲れるだろう

---

そこでIVFが活躍する

具体的には以下のように取り組む

1. データベースと撮影した生物情報等をベクトル変換
2. データベースにある生物情報をK-meansでクラスタリング
   • Ex.犬科クラスター(300品種)、猫科クラスター(100品種)、ゾウ科クラスター(3品種)などの2万科に分類される（仮）
3. 撮影した生物情報ベクトルと各クラスターのセントロイドのベクトルに対して、ベクトル検索
   • Ex.犬科, 猫科, ゾウ科, xx科の2万科に対してベクトル検索
4. 最も高い類似度となったクラスターに対して、ベクトル検索
   • Ex.犬科であれば、犬科の300品種に対してベクトル検索

これにより、800万品種の総当たりの必要性はなくなり、検索が高速化されたとさ
ちゃんちゃん

---

まあ今回の例でいけば事前に「科カラム」を定義しておけばいいんだけれどね

K-meansを用いて、人が具体的にカラム等を定義しなくても
いい感じにクラスター作って高速に検索するぜ〜ぐらいなイメージです

他にも様々なベクトル検索の効率化を図る手法があるようなので
色々調べてみようかなと思います

参考

How do inverted file (IVF) indexes work in vector databases, and what role do clustering centroids play in the search process?