Zenn
💭

IVF (Inverted File Index) とは？

に公開
未踏
中野哲平
楽天ブログ
ivf
hnsw
tech

FAISS (Facebook AI Similarity Search) の IVF+HNSW とは、FAISS の索引手法の一つで、Inverted File Index (IVF) と Hierarchical Navigable Small World (HNSW) を組み合わせた検索アルゴリズムです。

1. IVF (Inverted File Index) とは？

IVF は、大規模なベクトルデータの検索を高速化するための索引（クラスタリングベースの索引）です。

IVFの仕組み

  1. クラスタリング

    • ベクトル空間を K-means などを用いて 複数のクラスタ（セル） に分割する。
    • 各クラスタの中心を ボキャブラリー（codebook） とする。

  2. 割り当て

    • 各データベクトルを最も近いクラスタ（セル）に割り当て、逆ファイル（inverted list） に格納する。

  3. 検索

    • クエリベクトルが来たときに、全データではなく 近いクラスタ（セル）のみ検索 することで計算コストを削減する。

メリット：

  • 検索時に全データを対象としないため、高速化できる。
  • クエリと関係のないクラスタは無視できる。

デメリット：

  • クラスタの境界付近にあるデータの精度が低下する可能性がある。
  • クラスタリングによって検索精度が影響を受ける。

2. HNSW (Hierarchical Navigable Small World) とは？

HNSW は、高次元ベクトル検索のための グラフベースの近似最近傍探索アルゴリズム です。

HNSWの仕組み

  1. グラフの構築

    • ベクトル空間内のデータを ナビゲーション可能なスモールワールドグラフ (Navigable Small World Graph, NSW) に構築する。
    • 近傍のデータ同士をエッジで結び、階層的なグラフを形成する。

  2. 階層構造の利用

    • グラフには 複数のレベル があり、高レベルのノードは低レベルの広範囲をカバーする。
    • クエリベクトルは高レベルのノードからスタートし、徐々に細かいレベルへ降りながら最も近いデータを探索する。

  3. 検索時の近似最近傍探索

    • まずエントリポイント（初期ノード）から始めて、HNSWの階層的な探索を利用しながら近傍ノードを辿る。
    • 最近傍を探索することで、最終的に目的のベクトルに到達する。

メリット：

  • 高速な近似最近傍検索が可能。
  • クラスタの影響を受けにくい。
  • メモリ効率が良い。

デメリット：

  • 事前にグラフを構築する必要があり、インデックス構築に時間がかかる。
  • メモリ消費量が比較的大きい。

3. IVF + HNSW の組み合わせ

FAISS では、IVFとHNSWを組み合わせることで検索性能をさらに向上 させることができます。

IVF + HNSWの仕組み

  1. IVF に HNSW を適用

    • 各 IVF のクラスタ（セル）内のベクトルを HNSW グラフに格納する。
    • クエリが特定のクラスタに入った後、そのクラスタ内で HNSW を使って高速検索を行う。

  2. 検索の流れ

    • クエリベクトルを取得。
    • IVF により 適切なクラスタを選択（クラスタリングによる高速化）。
    • クラスタ内で HNSW によるグラフ探索（精度の向上）。

メリット

  • IVF により 検索対象のクラスタを絞る ことで検索速度を向上。
  • HNSW により クラスタ内での探索を高速化 し、精度を向上。
  • IVF の欠点（クラスタの境界問題）を HNSW が補う。

デメリット

  • インデックスの構築に時間がかかる。
  • メモリ使用量が増える（HNSWのグラフ構築があるため）。

4. FAISS における IVFFlat, IVF+HNSW, HNSW の違い

手法 仕組み 検索速度 精度 メモリ使用量
IVFFlat IVF のみ 速い 中 低
IVF+HNSW IVF + HNSW (クラスタ内でHNSW) 速い 高 中～高
HNSW HNSW のみ 遅い 高 高

5. いつ IVFFlat / IVF+HNSW / HNSW を使うべきか？

  • IVFFlat：メモリ消費を抑えたい＆高速検索が最優先
  • IVF+HNSW：検索速度と精度のバランスを取りたい
  • HNSW：高精度が最優先で、メモリ使用量は気にしない

6. コード例

FAISS で IVF+HNSW インデックスを作成するコード例：

import faiss
import numpy as np

# データセット（d次元ベクトル）
d = 128  # ベクトルの次元
nb = 100000  # データセットサイズ
nlist = 100  # IVF のクラスタ数
nprobe = 10  # 検索時のクラスタ探索数

# ランダムなデータセットを作成
np.random.seed(1234)
xb = np.random.random((nb, d)).astype('float32')

# IVF+HNSW インデックスを作成
quantizer = faiss.IndexHNSWFlat(d, 32)  # HNSW を使った量子化器
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)

# トレーニング（IVFのクラスタリング）
index.train(xb)
index.add(xb)  # データを追加

# クエリデータ
xq = np.random.random((10, d)).astype('float32')

# 検索
index.nprobe = nprobe  # 検索時のクラスタ数
D, I = index.search(xq, 5)  # 上位5件を検索

print(I)  # 近傍のインデックスを出力

まとめ

  • IVF+HNSW は、IVF のクラスタリング検索と HNSW のグラフ探索を組み合わせた手法。
  • IVF で検索範囲を絞り、HNSW でクラスタ内の探索を高速化＆精度向上。
  • 高速＆高精度を両立 したい場合に適している。

この手法は 大規模な類似検索（例えば画像検索、レコメンド、医用画像解析など）に活用できます。

Discussion