Engineering

近似最近傍探索（ANN）入門：ベクトル検索を支える仕組みを初心者向けに解説

概要

ChatGPTのようなLLMと社内文書を組み合わせるRAG（検索拡張生成）や、ECサイトの「あなたへのおすすめ」、画像の類似検索。これらの裏側では、ベクトル検索 という技術が動いています。そしてベクトル検索を実用的な速度で実現しているのが、本記事のテーマである ANN（Approximate Nearest Neighbor：近似最近傍探索） です。

本記事では、ANNとは何か、なぜ「近似」で良いのか、そしてANNシステムを構成する6つの要素（インデックス、量子化、距離計算、探索パラメータ、ストレージ戦略、前処理・後処理）を、初心者の方でも分かるように順番に解説します。

ANNとは何か

まずは「最近傍探索」から

最近傍探索（Nearest Neighbor Search）とは、たくさんのデータの中から「ある点に一番近いデータ」を見つける処理のことです。

ベクトル検索の文脈では、文章や画像はあらかじめ 埋め込みベクトル（Embedding） と呼ばれる数百〜数千次元の数値の配列に変換されています。意味が近い文章同士は、ベクトル空間上でも近い場所に配置されます。つまり「意味が似ている文章を探す」ことは「空間内で近いベクトルを探す」ことに置き換えられるのです。

最も素朴な方法は、クエリのベクトルと全データのベクトルを1件ずつ総当たりで比較することです。これを kNN（k-Nearest Neighbors：k近傍探索） の全探索（ブルートフォース）と呼びます。この方法は必ず正解を返しますが、データが1億件あれば1億回の距離計算が必要になり、リアルタイムの検索には到底間に合いません。

「近似」することで速くする

そこで登場するのがANNです。ANNは「100%正確な最近傍は保証しない代わりに、ほぼ正しい答えを桁違いに速く返す」というアプローチを取ります。

図書館で本を探す場面を想像してください。全部の棚を端から端まで見て回れば目当ての本は必ず見つかりますが、何時間もかかります。実際には「料理の棚はこのあたり」という分類を頼りに、関係がありそうな棚だけを見ますよね。まれに別の棚に置かれた本を見逃すかもしれませんが、ほとんどの場合は数分で目的の本にたどり着けます。ANNはまさにこの「あたりをつけて探す」仕組みをデータ構造として実現したものです。

全探索とANNの違い：全探索はすべての点と距離計算するのに対し、ANNは近そうな領域だけを調べる

検索精度は 再現率（Recall） という指標で測ります。例えば「真の上位10件のうち9件を返せれば再現率90%」です。実用上は、再現率95〜99%を保ちながら全探索の数百〜数千倍の速度を出す、といったバランスが狙いどころになります。

ANNシステムを構成する6つの要素

ANNは単一のアルゴリズムではなく、複数の技術の組み合わせで成り立っています。ここからは主要な6つの構成要素を順に見ていきます。

1. インデックス（探索用データ構造）

ANNの中心となるのが、高速に探索するためのデータ構造＝インデックスです。構築方式によって大きく3系統に分かれます。

グラフベースは、ベクトル同士を「近いもの同士」でつないだグラフを作り、グラフの辺をたどって近傍に近づいていく方式です。代表例は HNSW（Hierarchical Navigable Small World） で、現在最も広く使われています。高速道路網のように「長距離移動用の粗いつながり」と「近所を細かく回るつながり」を階層的に持つのが特徴です。ほかに NSG や、DiskANNで使われる Vamana があります。

HNSWの階層構造：上の層で大まかに近づき、下の層に降りて精密に探索する

検索はまばらな最上層のエントリーポイントから始まり、各層でクエリに近づけるだけ近づいてから下の層へ降りる、を繰り返します。上の層の「長距離ジャンプ」で一気に目的地の近くまで移動し、最下層で細かく探すことで、少ない計算回数で近傍にたどり着けます。

ツリーベースは、空間を木構造で再帰的に分割していく方式です。古典的な KD-tree や、Spotifyが開発した Annoy が代表例です。

ハッシュベースは、「近いベクトルは同じハッシュ値になりやすい」特殊なハッシュ関数を使う LSH（Locality Sensitive Hashing） が代表例です。

また、データをあらかじめクラスタ（グループ）に分けておき、クエリに近いクラスタだけを探索する IVF（Inverted File Index） もよく使われる方式です。

2. 量子化（Quantization）

量子化は、ベクトルを圧縮してメモリ使用量を減らし、距離計算を速くする技術です。インデックスと組み合わせて使われます。

  • SQ（Scalar Quantization）: 各次元の数値を float32 から int8 などに変換し、データ量を1/4程度に圧縮します
  • PQ（Product Quantization）: ベクトルを複数の部分空間に分割し、各部分を代表点の番号（コード）で表現します。圧縮率が高く、大規模データで定番の手法です
  • BQ（Binary Quantization）: 各次元を0/1のビットにまで圧縮し、ビット演算で距離計算を超高速化します

PQの考え方を図にすると次のようになります。ベクトルを部分に分割し、各部分を「代表点の番号」に置き換えることで、データ量を大幅に削減します。

PQの仕組み：ベクトルをサブベクトルに分割し、各部分を代表点のコードに置き換えて512バイトを4バイトに圧縮する

圧縮するほどメモリは節約できますが、元の情報が失われるため精度は下がります。ここでもトレードオフの調整が必要です。

3. 距離計算の手法

「近い」をどう定義するかも重要な選択です。主な距離（類似度）の指標には次のものがあります。

  • コサイン類似度: ベクトル同士の角度で類似度を測ります。文章の埋め込みでよく使われます
  • ユークリッド距離（L2）: 空間内の直線距離です
  • 内積（ドット積）: ベクトルの向きと大きさの両方を反映します

どれを選ぶべきかは、埋め込みを生成したモデルの特性に依存します。多くの埋め込みモデルは推奨の距離指標を公開しているので、それに合わせるのが基本です。

4. 探索パラメータ（チューニング）

ANNのインデックスには、精度と速度のトレードオフを調整する「つまみ」が用意されています。

HNSWの場合:

  • M: 各ノードが持つ接続（辺）の数。大きいほど精度が上がり、メモリ消費が増えます
  • ef_construction: インデックス構築時に調べる候補数。大きいほど質の良いグラフになり、構築時間が伸びます
  • ef_search: 検索時に保持する候補数。大きいほど再現率が上がり、検索が遅くなります

IVFの場合:

  • nprobe: 検索時に探索するクラスタ数。大きいほど精度が上がり、遅くなります

実際の運用では、自分のデータで再現率とレイテンシを測定しながら、要件を満たす最小のパラメータを探すのが定石です。

5. ストレージ戦略

データをどこに置くかも設計上の大きな分かれ目です。

  • インメモリ: 全データをメモリに載せる方式です。最速ですが、数億件規模になるとメモリコストが膨らみます
  • ディスクベース: DiskANN に代表される、インデックスの大部分をSSDに置く方式です。速度はやや落ちますが、メモリに載りきらない大規模データを現実的なコストで扱えます

6. 前処理・後処理

インデックスの外側にも、精度とコストを改善する工夫があります。

  • 次元削減（前処理）: PCAなどでベクトルの次元数を減らし、計算負荷とメモリを軽減します
  • リランキング（後処理）: ANNで粗く候補を絞り込んだ後（例：上位100件）、その候補だけを圧縮前のベクトルや厳密な距離計算で並べ替え直します。量子化で落ちた精度を、少ない追加コストで回復できる重要なテクニックです

実用システム設計の勘所

ここまで見てきた要素を組み合わせて、「速度・精度・メモリ・コスト」のバランスを設計するのが、実用的なANNシステム構築の勘所です。

特によく使われるのが、量子化＋インデックス＋リランキング の組み合わせです。

  1. PQなどで圧縮したベクトルをHNSWやIVFのインデックスに載せ、省メモリかつ高速に候補を絞り込む
  2. 絞り込んだ少数の候補だけを、元の精度の高いベクトルで並べ替え直す
flowchart LR
    A[クエリベクトル] --> B["ANNインデックスで粗く絞り込み
(HNSW / IVF + 量子化)"]
    B -->|"候補 上位100件"| C["リランキング
(元のベクトルで厳密に再計算)"]
    C -->|"上位10件"| D[最終結果]
クリックで拡大

この2段構えにより、「メモリは圧縮で節約しつつ、最終的な精度はリランキングで担保する」という良いとこ取りができます。大規模なベクトル検索システムで頻出のパターンなので、覚えておいて損はありません。

まとめ

本記事では、ANN（近似最近傍探索）の基本を解説しました。

  • ANNは「100%の正確さを少しだけ手放し、桁違いの速度を得る」技術で、RAGやレコメンドなどベクトル検索の基盤になっている
  • ANNシステムは、インデックス（HNSW、IVFなど）、量子化（PQ、SQ、BQ）、距離計算、探索パラメータ、ストレージ戦略、前処理・後処理という複数の要素の組み合わせで成り立つ
  • 設計の本質は「速度・精度・メモリ・コスト」のトレードオフ調整であり、量子化＋インデックス＋リランキングが定番パターン

FaissやMilvus、pgvectorなどのライブラリ・データベースを使えば、これらの仕組みを自分で実装せずに利用できます。ただし、パラメータの意味やトレードオフの構造を理解しているかどうかで、運用時のチューニングの質は大きく変わります。本記事がその土台になれば幸いです。

×