IVFとは

Inverted File Index / 転置ファイルインデックス

ベクトルをあらかじめクラスタへ分割し、検索時は近いクラスタのみを探索することで近似最近傍探索を高速化するインデックス構造

ひとことで言うと

ベクトルをグループ分けしておき、近いグループだけ調べて検索を速くする仕組み。

概要

IVF(Inverted File Index、転置ファイルインデックス)とは、大量のベクトルをk-means等でいくつかのクラスタへ分割し、各クラスタに属するベクトルの一覧(転置リスト)を保持しておくことで、近似最近傍探索(ANN)を高速化するインデックス構造。 検索時には、クエリベクトルに近いクラスタの中心(セントロイド)をいくつか選び、その周辺のクラスタに属するベクトルのみを対象に距離を計算する。全ベクトルと総当たりで距離を計算する場合と比べ、探索対象を絞り込める分、検索速度を大きく向上できる。 テキスト検索における転置インデックス(単語から文書への対応表)の発想をベクトル検索へ応用したもので、Product Quantization(積み量子化)等の圧縮手法と組み合わせて使われることが多く、Faiss等のライブラリで代表的なインデックス方式の1つとして実装されている。

背景

大規模なベクトル集合から類似ベクトルを検索する際、全ベクトルと総当たりで距離を計算する方式(Flatインデックス)は正確だが、データ量に比例して検索時間が増大する。IVFは、ベクトルをあらかじめクラスタへ分割し検索対象を絞り込むことで、精度をある程度保ちながら検索を高速化するために考案された。

歴史

IVFは、テキスト検索における転置インデックスの発想を近似最近傍探索へ応用したインデックス構造。 2011年: Hervé Jégouらが論文「Product Quantization for Nearest Neighbor Search」(IEEE TPAMI)にて、IVFとProduct Quantizationを組み合わせたベクトル検索手法を示した。 同手法は、後にMeta(旧Facebook)が公開したFaissの代表的なインデックス方式の1つとして実装されている。

アーキテクチャ

k-meansクラスタリングで得られた各セントロイドに対し、そのクラスタに属するベクトルのIDをまとめた転置リストを保持する。検索時はクエリに近いセントロイドをnprobe個選び、対応する転置リスト内のベクトルのみを対象に距離を計算する。クラスタ数やnprobeの値を調整することで、検索速度と精度のトレードオフを制御できる。

コード例

import faiss

d = 128       # ベクトルの次元数
nlist = 100   # クラスタ数

quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist)

index.train(xb)   # クラスタリングの学習
index.add(xb)     # ベクトルを追加

index.nprobe = 10 # 検索時に探索するクラスタ数
D, I = index.search(xq, k=4)

利点

• 全ベクトルとの総当たり計算と比べ、探索対象をクラスタ単位に絞り込むことで検索速度を大きく向上できる
• クラスタ数やnprobe等のパラメータで、検索速度と精度のトレードオフを調整できる

欠点

• クラスタの境界付近にある正解ベクトルを見逃す可能性があり、Flatインデックスと比べ検索精度は近似的になる
• クラスタリングの学習(トレーニング)が必要で、データ分布が大きく変化すると再学習を要する場合がある

比較

• HNSW — IVFがベクトルをクラスタへ分割し探索範囲を絞り込むのに対し、HNSWはグラフ構造をたどって近傍を探索する
• Faiss — IVFは、Faissで実装されている代表的な近似最近傍探索のインデックス方式の1つ
• 量子化 — IVFは、Product Quantization等の圧縮手法と組み合わせて使われることが多い
• ANN — IVFは、ベクトルをクラスタへ分割し探索範囲を絞り込む代表的なANNアルゴリズムの1つ

関連用語

よくある質問

参考文献

• Research PaperProduct Quantization for Nearest Neighbor Search