ANN(近似最近傍探索)とは?ベクトル検索を支えるHNSW・IVF・PQ・DiskANNの仕組みを徹底解説

ベクトル検索、そしてその中核をなすANN(Approximate Nearest Neighbor: 近似最近傍探索)は、いまや RAG(Retrieval-Augmented Generation)や推薦、画像検索など、機械学習を実サービスに組み込むほとんどの場面で登場する基盤技術になった。実務でベクトル検索基盤を選ぶとき、候補として最も頻繁に挙がるのが、専用ベクトルデータベースの代表格である Milvus と、全文検索エンジンにベクトル検索機能を統合した OpenSearch である。ところが、この2つを「使いこなせる」と言えるエンジニアは意外に少ない。理由ははっきりしている。どちらのドキュメントも「どう設定するか」は教えてくれるが、「なぜその設定で速くなる(あるいは遅くなる)のか」を体系立てて教えてくれないからだ。ef_search を上げると何が起きるのか。書き込み直後のデータが検索に出てこないのはバグなのか仕様なのか。セグメントが増えると遅くなるのはなぜか——こうした問いに答えるには、設定項目の暗記ではなく、その下にある ANN(Approximate Nearest Neighbor: 近似最近傍探索)の原理 と、それを分散システムとして実装したときに必然的に生じる構造の両方を理解する必要がある。

そこで本シリーズは、この理解を基礎の基礎から一段ずつ積み上げるために全3回に分けて書いた。原理から入り(原論文レベルで数式とアルゴリズムを解説する)、実装を読み(Milvus・OpenSearchそれぞれの設計論文とソースコードまで降りる)、最後に同じ土俵で比べる(両者を「同じANNの原理を異なる前提のもとで実装した2つの解」として並べる)——この3方針を、基礎編・Milvus編・OpenSearch編の3記事に分けて実践する。本記事はその第1回、基礎編である。全文検索とベクトル検索の関係から始め、埋め込み・距離・厳密探索を押さえた上でANNの主要4系統(HNSW / IVF / PQ / DiskANN)を原理から解説し、品質・速度・資源の測り方とベクトル検索基盤が専用化した理由を見た上で、どのエンジンにも共通する「ANN性能を支配する原理」を抽出する。後半ではベンチマークとPoC設計の作法、そしてMilvusとOpenSearchという2つの実装をどう選ぶかの判断フレームまでを扱う。各章の主張には可能な限り一次情報(論文・公式ドキュメント・ソースコード)へのリンクを付けたので、疑問に思った箇所は必ず原典に当たってほしい。巻末には論文でたどるANN研究の発展史(付録A)、用語集(付録B)、主要参照先(付録C)をまとめてある。

なお、本記事の内容は執筆時点(2026年7月)の情報に基づく。ANNまわりの実装は開発の速い分野であり、細部の仕様やパラメータ名は変わりうる。だからこそ本記事では、変わりにくい「原理」と「構造」に軸足を置いた。

本シリーズ「ANNとベクトル検索基盤の教科書」(全3回)

1. ANN基礎編(本記事)
2. Milvus内部構造編
3. OpenSearch内部構造編

RAG(検索拡張生成)を構築する文脈でベクトル検索を学びたい読者は、応用編として RAGとは?仕組みと構築の流れ も合わせて参照してほしい。

1. 全文検索とベクトル検索の違い: BM25の仕組みと語彙のミスマッチ

MilvusやOpenSearchを使いこなすためには、まず「検索エンジンが何を計算しているのか」を基礎から理解しておく必要がある。多くのエンジニアはすでに全文検索(full-text search)には親しんでいるはずなので、本章ではまず全文検索の仕組みを転置インデックス(inverted index)とBM25の数式レベルで確認し、それが本質的に不得意とすることを明らかにしたうえで、ベクトル検索(vector search)がどの問題を解決するために生まれたのかを示す。

転置インデックスとBM25

全文検索エンジンの心臓部は転置インデックスである。転置インデックスは、各単語(トークン)をキーとして、その単語が出現する文書IDのリスト(ポスティングリスト, posting list)を保持するデータ構造で、通常は文書内での出現頻度や出現位置も一緒に記録する。これにより「“検索"という語を含む文書はどれか」という問い合わせを、全文書を読まずにポスティングリストの参照だけで解決できる。

問題は、複数の候補文書が見つかったときにどう順位付けするかである。ここで使われるのが確率的検索モデルの到達点であるOkapi BM25である。BM25はStephen Robertsonらが1970〜80年代の確率的検索フレームワークを発展させて定式化したランキング関数で、“BM"は"Best Matching"の略、“25"は重み付けスキームの25番目の改良版であることに由来する( Wikipedia: Okapi BM25 )。

クエリ \(q=(q_1,\dots,q_n)\) と文書 \(D\) に対するBM25スコアは次式で与えられる。

ここで \(f(q_i, D)\) はクエリ語 \(q_i\) の文書 \(D\) 内での出現頻度、\(|D|\) は文書長、\(\text{avgdl}\) はコーパス全体の平均文書長である。\(k_1\) は出現頻度飽和の強さを制御するパラメータ(Luceneのデフォルトは \(k_1=1.2\) )、\(b\) は文書長正規化の強さを制御するパラメータ(デフォルト \(b=0.75\) 、範囲は \([0,1]\) )である。IDF項は原論文の定義では

であり、Lucene(OpenSearchの検索エンジン部分もこれを利用する)の実装ではスコアが負にならないよう \(\log\left(1 + \dfrac{N-n(q_i)+0.5}{n(q_i)+0.5}\right)\) という形が使われている( BM25Similarity, Lucene 7.0.1 API )。\(N\) はコーパス中の全文書数、\(n(q_i)\) は \(q_i\) を含む文書数である。式の意味は明快で、「珍しい語(IDFが大きい語)が」「文書長で正規化しつつ」「出現回数に応じて(ただし際限なく増えるのではなく飽和しながら)」スコアに寄与する、というものだ。

全文検索の得意・不得意

転置インデックス+BM25の枠組みは、語の完全一致(あるいは形態素解析後のトークン一致)に基づいているため、キーワードが的確に一致する場合には非常に高速かつ高精度に機能する。しかし本質的な弱点がある。それは語彙のミスマッチ(vocabulary mismatch)である。ユーザーが「車」と検索しても文書に「自動車」としか書かれていなければヒットしないし、“laptop"と検索しても"notebook computer"を含む文書は見つからない。同義語辞書やクエリ拡張である程度は緩和できるが、根本的には「文字列としての一致」を超えることができない。また、文の意味やニュアンス、“これに似た画像"のような非テキストの類似性を扱うこともできない。

ベクトル検索が解く問題

ベクトル検索は、テキストや画像を埋め込みモデル(embedding model、詳細は第2章)によって高次元の実数ベクトルに変換し、ベクトル空間内での距離や類似度によって「意味的に近いもの」を検索する。「車」と「自動車」は文字列としては全く異なるが、意味的にはほぼ同じ内容を指すため、良い埋め込みモデルはこれらを空間内の近い点に写像する。この意味検索(semantic search)によって、全文検索が原理的に解決できない語彙のミスマッチ問題に対応できる。ただし引き換えに、固有名詞の完全一致や数値・型番のような「意味ではなく表記が重要」な検索は苦手になりやすい。

図1-1のように、転置インデックスは語の文字列一致でしか文書にたどり着けないため「車」というクエリが「自動車」を含む文書に届かないのに対し、ベクトル空間では両者が意味的に近接した点として配置されるため、クエリの近傍円が両方を捉えられる。この対比が全文検索とベクトル検索の本質的な違いである。

図1-1: 転置インデックス(左)は語の文字列一致に基づくため語彙のミスマッチを解決できないが、ベクトル空間(右)では意味的に近い語が幾何学的にも近接するため、クエリの近傍円が両方を捉えられる。

両者の関係:ハイブリッド検索とRRF

この相補性から、実務では全文検索とベクトル検索を組み合わせるハイブリッド検索(hybrid search)が広く使われる。課題は、BM25のスコア(理論上上限のない実数)とベクトル検索の距離・類似度スコア(メトリックにより範囲が異なる)を、どう1つのランキングに統合するかである。

よく使われる解法がReciprocal Rank Fusion(RRF)である。RRFはGordon Cormackらが2009年のSIGIR論文で提案した手法で、各検索結果リストにおける「生スコア」ではなく「順位」だけを使う( Cormack et al., “Reciprocal Rank Fusion outperforms Condorcet and Individual Rank Learning Methods”, SIGIR 2009 )。文書 \(d\) の統合スコアは

で計算される。ここで \(\text{rank}_i(d)\) は \(i\) 番目の検索結果リストにおける \(d\) の順位、\(k\) は平滑化パラメータで経験的に \(k=60\) が広く使われる。\(k\) を大きくすると上位順位の影響が薄まり、小さくすると1位の結果が支配的になる。

Milvusの公式ドキュメントにある具体例を見ると仕組みがよくわかる。疎ベクトル(全文検索的な検索)でID 101が1位、密ベクトル(意味検索)で2位だったとすると、\(k=60\) のとき

となり、これが他候補と比較されて最終順位が決まる( Milvus: RRF Ranker )。RRFはスコアのスケールを気にせず複数の検索方式を「民主的に」統合できるため、全文検索とベクトル検索という性質の全く異なる2つのスコアを混ぜるハイブリッド検索の標準的な手法になっている。この考え方は、 Milvus内部構造編 ・ OpenSearch内部構造編 でそれぞれの具体的なハイブリッド検索APIを見るときの土台になる。

2. 埋め込みベクトルと距離計算: コサイン類似度・内積・L2距離の使い分け

埋め込みモデルの役割

ベクトル検索の入力となる埋め込みベクトル(embedding vector)は、テキストや画像などを固定長の実数ベクトルに変換したものである。埋め込みモデルは「意味的に近いものは幾何学的にも近い点になる」ように学習されており、この性質があって初めて距離計算による検索が意味を持つ。

次元数(dimensionality)はモデルによって様々である。例えばOpenAIのtext-embedding-3-smallは1536次元、text-embedding-3-largeは最大3072次元のベクトルを生成し、後者はdimensionsパラメータで次元を切り詰めても性能劣化が少ないよう学習されている( OpenAI: New embedding models and API updates )。多言語対応のBAAI/bge-m3やintfloat/multilingual-e5-largeはいずれも1024次元のdenseベクトルを出力する( BGE-M3 model card, NVIDIA Build )。次元数はそのままインデックスのメモリ使用量に直結するため(第4章で具体的な計算式を扱う)、精度と資源消費のトレードオフを考えるうえで重要な前提になる。

L2距離・内積・コサイン類似度

ベクトル間の「近さ」を測る代表的な指標は3つある。\(n\) 次元ベクトル \(a=(a_0,\dots,a_{n-1})\) 、\(b=(b_0,\dots,b_{n-1})\) に対して、

ユークリッド距離(L2距離)

は2点間の直線距離であり、小さいほど類似している。

内積(Inner Product, IP)

は大きいほど類似しているとみなす。正規化されていないベクトル同士では大きさ(ノルム)の影響を受けるため、ノルムが大きいベクトルが常に「似ている」と判定されやすいという性質がある。

コサイン類似度

は2ベクトルのなす角のみに着目し、大きさの影響を排除する。範囲は \([-1,1]\) で、1に近いほど類似している。

3つの指標はどれを使うべきかという疑問が当然出るが、実はベクトルをL2正規化(単位ベクトル化)しておけば、コサイン類似度・内積・L2距離は互いに単調な関係になり実質的に等価になる。\(a'=a/\|a\|\) 、\(b'=b/\|b\|\) とすると、

が成り立つ(Milvusの公式ドキュメントもこの正規化関係を明示している。 Milvus: Similarity Metrics )。つまり正規化済みベクトルであれば、コサイン類似度が高い(\(\cos\theta\) が1に近い)ことと、L2距離が小さいこと、内積が大きいことは全て同じ順位付けを与える。これが「埋め込みを正規化してから内積(IP)インデックスを使う」という実装がしばしば採用される理由である。逆に正規化していないベクトルに対してL2とIPを使うと異なる検索結果になり得るので注意が要る。

図2-1のように、正規化前のベクトル\(a,b\) ではL2距離となす角\(\theta\) は別々の量だが、両者を単位円上に射影すると\(\|a'-b'\|^2=2-2\cos\theta\) という関係でL2距離と角度(=コサイン類似度)が1対1に結びつく。

図2-1: ベクトルを単位円上に正規化すると、L2距離の2乗が\(2-2\cos\theta\) という形でなす角と直接結びつき、L2距離・内積・コサイン類似度が互いに単調な関係(実質的に等価)になることが幾何学的にわかる。

距離からスコアへの変換

ANNエンジンの多くは、内部の「距離」(小さいほど良い、または大きいほど良い、指標によって向きがバラバラ)を、ユーザー向けに「大きいほど良い」統一されたスコアに変換して返す。この変換式は各エンジンの実装依存であり、仕様として明記されている。

OpenSearchは空間(space)ごとに次のスコア変換式を定義している( OpenSearch: Spaces )。

コサイン類似度の場合、内部的には「距離」として \(1-\cos\theta\) を使う(小さいほど類似)ため、スコアに戻すときに \((2-d)/2\) という変換で \([0,1]\) に写像し直している。内積のように符号が変わりうる指標では、\(d\) の符号で場合分けした区分関数になっている点が実装上のポイントである。

Milvusはハイブリッド検索(第1章のRRF/WeightedRanker)でスコアを \([0,1]\) に揃えるためにarctan関数を採用している。GitHub上のソースコード議論によれば、内部の変換式は

である( milvus-io/milvus Discussion #34415 )。L2は \([0,\infty)\) 、IPは \((-\infty,\infty)\) という無限の値域を持つため、\(\arctan\) を使うことで有限区間 \([0,1]\) に滑らかに写像している。COSINEはもともと \([-1,1]\) に収まっているため線形変換で十分、という設計判断である。この違いを知っておくと、複数の指標を跨いだハイブリッド検索のスコアがなぜあのような形になるのか腑に落ちるはずだ。

3. k-NN(厳密探索)とANN(近似最近傍探索): なぜ近似が必要なのか

brute-force kNNの計算量

「クエリベクトルに最も近い \(k\) 個のベクトルを求める」という最近傍探索(k-nearest neighbor search, kNN)を素朴に解くなら、クエリと全データ点との距離を計算して並べ替えればよい。データ点数を \(N\) 、次元数を \(d\) とすると、距離計算に \(O(N \cdot d)\) 、上位 \(k\) 件の抽出に \(O(N \log k)\) (ヒープを使う場合)かかる。これがbrute-force(全数探索、厳密探索とも呼ぶ)である。

厳密で実装も単純だが、\(N\) が数百万〜数十億のオーダーになると、1クエリあたりの計算コストが線形に増大し、実用的なレイテンシを維持できなくなる。手元の実験でも、10万点×128次元のデータに対してNumPyで内積を全計算するbrute-forceは1クエリあたり約7.1msかかった(後述の実験、queries @ data.Tによるバッチ計算)。\(N\) が10倍になればこの時間もおおよそ10倍になる。

curse of dimensionality(次元の呪い)

次元数が増えるにつれ、直感に反する現象が起きる。Beyerらの研究"When is ‘Nearest Neighbor’ Meaningful?“は、ある条件下では次元数が増えるほど、任意の点から見た「最も近い点」と「最も遠い点」の距離の差が0に収束していくことを示した( Beyer et al., 1999 )。つまり高次元空間では全ての点がほぼ等距離に見えてしまい、「近傍」という概念自体が意味を失いかねない。

この現象は索引構造の実用性にも直接影響する。Weber・Schek・Blottの研究は、R*-treeなどの空間分割型索引が、次元数がおよそ10を超えたあたりで単純な逐次スキャン(sequential scan)に計算量で追い抜かれることを定量的に示した( Weber, Schek, Blott, “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces”, VLDB 1998 )。埋め込みベクトルは数百〜数千次元に及ぶことが普通なので、伝統的な木構造索引(第7章で詳しく扱う)は原理的にこの壁にぶつかる。

一方で、この「次元の呪い」の効き方はデータの分布に強く依存する。完全に一様ランダムな高次元データでは最悪ケースに近い挙動を示すが、実際のテキスト・画像埋め込みは意味的なクラスタ構造を持っているため、同じ次元数でもはるかに扱いやすい。この違いは本記事の実験(第4章・第5章)で具体的な数値として確認する。

なぜ近似が必要か

curse of dimensionalityと、brute-forceの線形計算量という2つの事実を組み合わせると、「大規模かつ高次元のデータに対して、レイテンシとメモリの制約の中で厳密な最近傍を求め続けるのは非現実的」という結論に至る。そこで登場するのが近似最近傍探索(Approximate Nearest Neighbor search, ANN)である。ANNは「本当に最も近い \(k\) 点」を保証する代わりに、「高い確率でそれに近い集合」を、厳密探索よりずっと少ない計算量で返すことを目指す。

recallの定義

近似がどれだけ「良い」かを測る基本指標が再現率(recall)である。ANN文脈でのrecall@k(しばしばrecall@10のように書く)は、クエリごとに次のように定義される。

ここで \(S_{\text{exact}}\) はbrute-forceで求めた真の上位 \(k\) 件の集合、\(S_{\text{approx}}\) はANNアルゴリズムが返した上位 \(k\) 件の集合である。これを多数のクエリについて平均したものが、一般に報告される recall@k の値になる。ann-benchmarks.comもこの定義、すなわち「平均して真の近傍が見つかった割合」をrecallの定義として採用している( ann-benchmarks.com )。

ANNの定式化

ANNは形式的には次のように定式化できる。データ集合 \(X=\{x_1,\dots,x_N\}\subset\mathbb{R}^d\) とクエリ \(q\in\mathbb{R}^d\) が与えられたとき、真の\(k\) -最近傍集合 \(S_{\text{exact}}(q,k)\) に対して、ある許容誤差のもとで

を満たすように \(S_{\text{approx}}\) を計算量 \(o(N)\) (多くの場合 \(O(\log N)\) や \(O(\sqrt{N})\) 程度)で求める、という問題として捉えられる。ここで \(\epsilon\) は許容する取りこぼし率、\(\delta\) はその保証が成り立つ確率である。実務的には、この確率的な保証を厳密に扱うというより、「候補数を増やせばrecallは上がるが計算量も増える」というパラメータ付きのトレードオフとして扱うのが一般的で、この考え方が第4章で紹介するHNSWやIVFの中心的なパラメータ(ef、nprobeなど)の意味を理解する鍵になる。

4. ANNアルゴリズム4系統の仕組み: HNSW・IVF・PQ・DiskANN

ANNアルゴリズムは無数に存在するが、実務でMilvusやOpenSearchを使う上でまず押さえるべきは次の4つである。これらは互いに排他的ではなく、しばしば組み合わせて使われる(例えばIVFとPQを組み合わせたIVFPQ、DiskANNはグラフ型とディスク最適化の組み合わせ)。本章ではこれらを次の4つの型として整理する。

• グラフ型: HNSW ― ベクトルをノードとするグラフを構築し、貪欲法でグラフを辿って近傍にたどり着く
• 空間分割型: IVF(Inverted File) ― 空間をクラスタに分割し、クエリに近いクラスタだけを探索する
• 圧縮型: PQ(Product Quantization) ― ベクトルを圧縮し、近似距離を高速に計算する
• ディスク型: DiskANN ― グラフ型索引をSSD上に置くことを前提に設計する

グラフ型:HNSW

HNSW(Hierarchical Navigable Small World)は、Yu. A. MalkovとD. A. Yashuninが2016年に発表した論文で提案された( Malkov & Yashunin, arXiv:1603.09320 )。この論文はhnswlibやMilvus、OpenSearch(NMSLIBおよびLuceneのHNSW実装、Faissエンジン経由)など、現在広く使われるほぼ全てのHNSW実装の理論的基盤になっている。

NSWからHNSWへ。HNSWの前身であるNavigable Small World(NSW)は、単一階層のグラフ上で貪欲探索を行う手法で、多対数(polylogarithmic)の探索計算量を持つことが知られていた。しかし単一階層では、探索の初期段階で「大まかに近いエリア」にたどり着くまでのホップ数が支配的コストになってしまう。HNSWはこれを解決するために、スキップリスト(skip list)にヒントを得た階層構造を導入した。上位層ほどノード数が少なく長距離のリンクを持ち、下位層に向かうほどノードが密になり短距離のリンクが増える。探索は最上位層から始めて貪欲法で「大まかな位置」を素早く特定し、階層を降りるごとに探索を精密化していく。この構造により、論文は理論的にも実験的にも対数(logarithmic)オーダーへの計算量の改善を主張している。

層構造とパラメータ。各要素が持つ最大階層 \(l\) は、正規化定数 \(m_L\) を使った指数分布に従ってランダムに決まる。

論文は \(m_L\) の実用的な既定値として

を提案している。これはスキップリストにおける段飛ばし確率 \(p=1/M\) に対応し、層間で平均1要素程度のオーバーラップが生まれるよう調整された値である。

パラメータの意味は次の通りである。

• M: 挿入時に各ノードに張る接続数(次数)の目安。大きいほどrecallは上がるがメモリと構築時間が増える。論文では実用上最適な \(M\) はおおむね6〜48の範囲にあるとされる。
• efConstruction: インデックス構築時に、各ノードの近傍候補を探すために保持する動的候補リストのサイズ。大きいほど質の良いグラフができるが構築が遅くなる。
• efSearch(論文では単に \(ef\) ): 検索時に保持する動的候補リストのサイズ。大きいほどrecallが上がるがレイテンシも増える。

挿入・探索アルゴリズム。論文のAlgorithm 1(INSERT)とAlgorithm 2(SEARCH-LAYER)を要約した擬似コードは次の通りである。

INSERT(hnsw, q, M, Mmax, efConstruction, mL)
  W ← ∅
  ep ← hnswのエントリポイント
  L ← epの最上位層
  l ← floor(-ln(unif(0,1)) * mL)      # 新要素の最大層
  for lc ← L downto l+1:
      W ← SEARCH-LAYER(q, ep, ef=1, lc)
      ep ← Wの中でqに最も近い要素
  for lc ← min(L,l) downto 0:
      W ← SEARCH-LAYER(q, ep, efConstruction, lc)
      neighbors ← SELECT-NEIGHBORS(q, W, M, lc)   # ヒューリスティック選択
      layer lc 上で q と neighbors の間に双方向リンクを張る
      各近傍ノードの接続数が Mmax(層0ではMmax0)を超えたら刈り込む
      ep ← W
  if l > L: hnsw のエントリポイントを q に更新

SEARCH-LAYER(q, ep, ef, lc)
  v ← {ep}          # 訪問済み集合
  C ← {ep}          # 候補集合(最近傍優先キュー)
  W ← {ep}          # 現時点でのef個の近傍(最遠優先キュー)
  while C が空でない:
      c ← Cの中でqに最も近い要素
      f ← Wの中でqから最も遠い要素
      if dist(c,q) > dist(f,q): break   # 打ち切り条件
      for e in cの近傍(層lc):
          if e が未訪問:
              v に e を追加
              f ← Wの中でqから最も遠い要素
              if dist(e,q) < dist(f,q) or |W| < ef:
                  C, W に e を追加
                  if |W| > ef: Wから最遠要素を除去
  return W

探索(K-NN-SEARCH)はこのSEARCH-LAYERを最上位層から順に呼び出し、層0での探索結果を最終的な近傍候補として返す(最初の層降下では \(ef=1\) の単純な貪欲探索、層0でのみ \(ef\) を本来の値に上げる)。この2フェーズ構造こそが「efSearchを大きくするとrecallが上がりレイテンシも増える」というトレードオフの実体である。

図4-1のように、上層ほどノード数が疎で長距離のリンクを持ち、下層ほど密になる。探索はエントリポイントから最上位層で貪欲法により大まかな位置を特定し、階層を降りるごとに精密化していく。

図4-1: HNSWの階層構造。上層(疎)ほど長距離の飛び先を持ち、下層(密)ほど近傍を精密に辿れる。探索はエントリポイントから始め、赤矢印のように階層を降りるたびに探索範囲を絞り込みながらクエリ点に近づいていく。

メモリ量の概算。論文はHNSWのメモリ消費を次のように見積もっている。層0での接続数上限を \(M_{max0}\) 、それ以外の層を \(M_{max}\) とすると、要素あたりの平均メモリ消費は

であり、\(M\) が6〜48の実用的な範囲では、ベクトル本体を除いて要素あたり約60〜450バイトになるとしている(4バイト整数でリンクを表現する場合)。実装レベルではFaissのHNSWインデックスのメモリ使用量は概算式 (d*4 + M*2*4) バイト/ベクトルとして公開されている( faiss wiki: Faiss indexes )。\(d\) は次元数、\(M\) はグラフの次数である。次元数分の生ベクトル(4バイト float × \(d\) )とグラフ接続情報の合計、という直感的な式になっている。

空間分割型:IVF

IVF(Inverted File index)はk-meansなどのクラスタリングでベクトル空間を nlist 個のセル(クラスタ)に分割し、各ベクトルを最も近いセルの転置リストに割り当てる。検索時には、クエリに最も近い nprobe 個のセルだけを走査する。全探索が \(N\) 点を舐めるのに対し、IVFはおよそ \(N/\text{nlist} \times \text{nprobe}\) 点だけを距離計算すればよいので、nprobe を増やせばrecallは上がるが計算量も増える、というシンプルなトレードオフになる。Faissの公式ガイドラインは、データ規模が100万未満の場合の目安として nlist を \(4\sqrt{N}\) から \(16\sqrt{N}\) 程度に設定することを推奨している( faiss wiki: Guidelines to choose an index )。nlist が小さすぎると1セルあたりの点数が多くなり絞り込みの効果が薄れ、大きすぎるとクラスタ数分の粗量子化探索自体のコストが増える。

図4-2のように、クラスタ中心(セントロイド)群はボロノイ図としてセルに空間を分割し、クエリに近いnprobe個のセルだけが探索対象になり、残りはスキップされる。

図4-2: IVFのボロノイ分割。各セルは1つのセントロイドが担当する領域を表し、クエリ(星印)に近いnprobe個のセル(濃いオレンジ)だけが実際に探索され、他のセル(グレー)は探索がスキップされる。

圧縮型:PQ(Product Quantization)

PQはHervé Jégou、Matthijs Douze、Cordelia Schmidが2011年のIEEE TPAMIに発表した手法で( Jégou, Douze, Schmid, “Product Quantization for Nearest Neighbor Search,” IEEE TPAMI 33(1), 2011 )、ベクトルの圧縮によってメモリ使用量と距離計算コストを大幅に削減する。

考え方はこうだ。\(d\) 次元ベクトル \(x\) を \(M\) 個のサブベクトルに分割する。

各サブ空間ごとに独立してk-meansなどでコードブック(codebook)を学習し、\(k^{*}\) 個(典型的には \(k^{*}=256\) 、つまり1サブベクトルあたり \(\log_2 256=8\) ビット)のセントロイド \(c_{m,1},\dots,c_{m,k^{*}}\) を得る。ベクトル \(x\) は、各サブベクトルを最も近いセントロイドのインデックスに置き換えることで、\(M\) 個の8ビットコード(= \(M\) バイト)に圧縮される。1024次元のベクトルで \(M=96\) のように分割するのが実務でよく見る設定である。

検索時に使われるのが非対称距離計算(Asymmetric Distance Computation, ADC)である。クエリベクトル \(q\) 自体は量子化せず生のまま保持し、\(q\) を同じ \(M\) 個のサブベクトルに分割したうえで、各サブ空間ごとに「クエリのサブベクトルと、そのサブ空間の全セントロイドとの距離」を事前計算してルックアップテーブルを作る。

データベース側の各ベクトルとの距離は、このテーブルを引いて足し合わせるだけで近似できる。

これによって、実ベクトル同士のユークリッド距離計算(乗算 \(d\) 回)を、テーブル参照+加算(\(M\) 回)に置き換えられる。対称距離計算(Symmetric Distance Computation, SDC)はクエリ側も量子化してしまう方式で、圧縮率は上がるが精度はADCに劣る。IVFと組み合わせたIVFPQでは、粗量子化器(IVFのセントロイド)からの残差ベクトル(residual)、すなわち「そのクラスタ中心からのズレ」をPQで符号化することで、粗い位置情報と細かい形状情報を分担させている( faiss wiki: Faiss indexes )。メモリ使用量はコードサイズがそのまま効くので、IndexIVFPQで概算 ceil(M*nbits/8)+8 バイト/ベクトル(末尾8バイトはベクトルID分)という式が示されている。

図4-3のように、元の1024次元ベクトルをM=8個のサブベクトルに分割し、各サブ空間で学習したコードブックの中から最も近いセントロイドのインデックスに置き換えることで8バイトのコードに圧縮する。検索時はクエリ側のみルックアップテーブルを作り、コードを引いて総和するだけで距離を近似する(ADC)。

図4-3: PQのエンコード手順とADC。元ベクトルをM個のサブベクトルに分割してそれぞれ最も近いセントロイドのインデックスに置き換えることで大幅に圧縮し、検索時はクエリ側だけルックアップテーブルを引いて距離を近似する。

ディスク型:DiskANN

DiskANNはSuhas Jayaram Subramanyaらが2019年のNeurIPSで発表したシステムで、SSD上に十億点規模のインデックスを載せて、64GBというコモディティなRAM量でも高いrecallと低レイテンシを実現することを目的としている( Subramanya et al., “DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node,” NeurIPS 2019 )。

その中核となるグラフ構築アルゴリズムがVamanaである。Vamanaは貪欲探索GreedySearchと、次数を制限する枝刈りアルゴリズムRobustPruneの2つで構成される。RobustPruneは、点 \(p\) の近傍候補集合 \(V\) から次数上限 \(R\) 個の近傍を選ぶ際に、距離しきい値パラメータ \(\alpha \ge 1\) を使い、\(p^{*}\) を候補の中で最も近い点として選んだあと、

という操作を繰り返す。\(\alpha\) を1より大きくすることで、単なる最近傍だけでなく「長距離の飛び先」となるエッジも意図的に残す設計になっており、これがHNSWやNSGに比べて少ないホップ数でグラフを辿り切れる理由になっている(論文はHNSW・NSGに比べ2〜3倍少ないホップ数で収束すると報告している)。

DiskANNのシステム設計では、フルサイズのベクトルとグラフ構造をSSD上に置き、PQで圧縮したベクトルだけをRAM上にキャッシュする。これにより、クエリ経路上のほとんどの距離計算はRAM上の圧縮ベクトルで近似的に済ませ、SSDへのランダムアクセス回数を最小限に抑える。論文中の実験パラメータの例では、SIFT1Mなど100万点規模のインメモリ比較実験でVamanaのグラフパラメータを \(L=125,\ R=70,\ C=3000,\ \alpha=2\) と設定し(比較対象のHNSWは \(M=128,\ efC=512\) )、10億点のANN_SIFT1Bデータセットでは、単一ショットで \(L=125,\ R=128,\ \alpha=2\) のインデックスを構築するとピークメモリ約1100GB・構築に2日を要した一方、40個のシャードに分割してそれぞれ \(R=64\) で構築後にマージする方式ではメモリ使用量を64GB未満に抑えつつ348GBのインデックス(5日で構築)を得ている。最終的な検索性能は、16スレッドで実行した場合に秒間5000件以上のクエリを、平均レイテンシ3ms未満、recall@1 95%以上で処理できたと報告されている。

図4-4のように、RAM上にはPQ圧縮ベクトルのみを載せて候補を粗く絞り込み、フル精度ベクトルとVamanaグラフはSSDに置いて絞り込んだ候補についてのみ最小限のランダムリードを行う、という2段構えの設計がRAM使用量をデータ規模に対しほぼ一定に保つ鍵になっている。

図4-4: DiskANNのメモリ階層。RAMにはPQ圧縮ベクトルだけを置いて候補を粗く絞り込み(①)、絞り込んだ候補についてのみSSDへ最小限のランダムリードを行い(②)、フル精度ベクトルで再計算・再ランクする(③)ことで、RAM使用量をデータ規模に対しほぼ一定に保っている。

メモリ量の比較という視点

4手法のメモリに対する考え方をまとめると次のようになる。

• HNSW: ベクトル本体(次元数に比例)+グラフ接続情報(\(M\) に比例)を全てRAMに保持する。recallと速度は高いがメモリ効率は良くない。
• IVF(Flat): ベクトル本体はほぼそのまま保持するが、走査対象をnprobeセルに絞ることで計算量を削減する。メモリはHNSWと大差ないが、グラフ接続情報を持たない分やや軽い。
• PQ / IVFPQ: ベクトルをコード(典型的にはM〜数十バイト)に圧縮するため、メモリ使用量を桁違いに削減できる。ただし圧縮によりrecallの上限は下がる。
• DiskANN: フルベクトルとグラフをSSDに置き、圧縮ベクトルのみRAMに持つことで、RAM使用量をデータ規模に対してほぼ一定に保ちながら十億点規模までスケールする。

どれを選ぶかは「精度」「速度」「メモリ・ディスク」という3軸のどこを優先するかで決まる。次章ではこの3軸を測定する具体的な方法を扱う。

5. ANNの評価指標: recall・QPS・レイテンシ・メモリの測り方

ANNアルゴリズムやそのパラメータを比較するとき、単一の「これが一番良い」という答えは存在しない。品質(recall)、速度(QPS・レイテンシ)、資源(メモリ・ディスク)は独立した軸であり、どれか1つを改善すると別の軸が悪化するのが通常だからだ。本章ではこれらを測定するための具体的な指標を確認する。

recall@k、QPS、レイテンシ

recall@k は第3章で定義した通り、真の上位\(k\) 件のうちどれだけをANNが返せたかの平均割合である。**QPS(Queries Per Second)**は単位時間あたりに処理できるクエリ数で、スループットの指標である。レイテンシは1クエリを処理するのにかかった時間で、単純平均だけでなく、分布のパーセンタイル値、特に p50(中央値)・p95・p99 を見ることが重要である。平均値は少数の遅いクエリに引きずられにくいが、ユーザー体験やSLAを議論する上では「95%のクエリはこの時間以内に返る」というp95、稀な遅延の最悪ケースに近いp99の方が実務的な意味を持つ。

メモリ・ディスク使用量も無視できない軸である。第4章で見たように、同じデータ規模・同じrecallを達成するにも、HNSWとPQ圧縮版とでは必要なメモリが桁違いに変わりうる。

recall-QPSトレードオフ曲線

ANNアルゴリズムの性能を報告するときの標準的な作法は、候補数パラメータ(HNSWならefSearch、IVFならnprobe)を振りながらrecallとQPS(またはレイテンシ)を同時に測定し、両者の関係を曲線として描くことである。これをrecall-QPSトレードオフ曲線と呼ぶ。この曲線が右上(高recallかつ高QPS)にあるほど優れたアルゴリズム・実装ということになる。

手元でもこの曲線を実際に測定してみた。10万点×128次元の合成データを2種類用意し(1つは完全にランダムな一様分布、もう1つは50個のクラスタを持つ、実際のembeddingに近い分布)、hnswlibでM=16、efConstruction=200のHNSWインデックスを構築し、efSearchを10から800まで変えながらrecall@10とQPS(バッチクエリをマルチスレッドで処理したときのスループット)を測定した。

import numpy as np
import hnswlib

rng = np.random.default_rng(42)
N, D, NQ, K = 100_000, 128, 200, 10

data = rng.standard_normal((N, D), dtype=np.float32)
data /= np.linalg.norm(data, axis=1, keepdims=True)
queries = rng.standard_normal((NQ, D), dtype=np.float32)
queries /= np.linalg.norm(queries, axis=1, keepdims=True)

# brute-forceで正解(ground truth)を作る
sims = queries @ data.T
gt_idx = np.argsort(-sims, axis=1)[:, :K]

# HNSWインデックスを構築
index = hnswlib.Index(space='ip', dim=D)
index.init_index(max_elements=N, ef_construction=200, M=16, random_seed=100)
index.add_items(data, np.arange(N))

for ef in [10, 20, 50, 100, 200, 400, 800]:
    index.set_ef(ef)
    labels, _ = index.knn_query(queries, k=K)
    recall = np.mean([
        len(set(labels[i]) & set(gt_idx[i])) / K for i in range(NQ)
    ])
    print(ef, recall)

結果は図5-1の通りである。

図5-1: efSearchとrecall@10の関係。一様ランダムなデータ(青)ではefSearchを上げても頭打ちになるのに対し、クラスタ構造を持つデータ(オレンジ)ではより低いefSearchで高いrecallに達する。

一様ランダムなデータでは efSearch=800 まで上げてもrecall@10は0.86程度にしか達しない。これに対し、クラスタ構造を持つデータ(実際のテキスト・画像embeddingにより近い)では efSearch=100 程度で早くもrecall@10が0.96に達し、efSearch=800では0.995まで到達する。これは第3章で述べたcurse of dimensionalityの効き方がデータの構造に強く依存するという主張を、具体的な数値で裏付けている。

同じ測定からrecallとQPSの関係を描いたのが図5-2である。

図5-2: recall-QPSトレードオフ曲線。efSearchを振りながらrecallとQPSを同時に測定し、右上(高recallかつ高QPS)にあるほど優れた設定であることを示す。

recallを上げようとするとQPSが指数的に近い形で低下していく古典的なトレードオフの形が確認できる。クラスタ構造のあるデータでは同じrecall水準をより高いQPSで達成できており、この曲線が「右上にあるほど良い」という見方を体感できる。ann-benchmarks.comもまさにこの形式でアルゴリズムを比較しており、glove-100-angularやsift-128-euclideanなど公開データセットに対し、単一クエリ(バッチ化しない)を基本設定として、標準化されたAWSインスタンス上でrecallとQPSを測定し、複数アルゴリズム・複数パラメータの結果をこの座標系にプロットする、という手法を採用している( ann-benchmarks.com , erikbern/ann-benchmarks README )。パラメータを網羅的に振ったうえで、recall-QPS平面上のパレートフロンティア(他のどの設定にもrecallとQPSの両方で負けない点の集合)だけを結果として採用するのが、公平な比較のための重要な作法である。

6. ベクトル検索が遅い原因の分解: ボトルネックの特定方法

「ベクトル検索が遅い」という現象に直面したとき、原因を特定するにはまず1クエリの処理時間がどこに費やされているかを分解する必要がある。典型的な内訳は次の通りである。

1. ネットワーク/キューイング: クライアントからリクエストが届き、サーバー内のワーカーに割り当てられるまでの時間。負荷が高いとここでの待ち行列(キューイング)遅延が支配的になることがある。この待ち行列遅延の定量的なモデル化には、https://yuhi-sa.github.io/posts/20260716_db_pool_queueing/1/で扱ったM/M/c待ち行列モデルの考え方がそのまま適用できる。
2. インデックス走査: HNSWならグラフの探索、IVFならプローブ対象クラスタの走査など、候補集合を絞り込むための処理。
3. 距離計算: 候補となったベクトルとクエリとの実際の距離・類似度計算。PQのようにテーブルルックアップで済ませる場合と、生ベクトルで正確に計算し直す場合がある。
4. 再ランク(reranking): 圧縮ベクトルなどで粗く絞った候補集合に対し、フル精度のベクトルで再計算して順位を精緻化するステップ。
5. 結果マージ: 複数のセグメントやシャードから返ってきた部分的な上位k件を1つの最終結果にまとめる処理(ハイブリッド検索であればRRFなどの統合もここに含まれる)。

図6-1のように、efSearchを大きくすると主にインデックス走査と距離計算の成分が伸びる一方、ネットワーク/キューイングや結果マージはほぼ一定のままである。

図6-1: 1クエリのレイテンシ内訳(概念図であり実測値ではない)。efSearchを上げると主にインデックス走査(青)と距離計算(オレンジ)の成分が伸び、ネットワーク/キューイングや結果マージはほぼ一定に留まる。

この分解を意識すると、「efSearchやnprobeを上げてもレイテンシが線形にしか増えないはずなのに、実際には急激に悪化する」といった現象の原因を、キューイング遅延や再ランクコストなど別の要素に切り分けて調べられるようになる。

候補数パラメータとレイテンシの関係

第4章・第5章で見たefSearch(HNSW)やnprobe(IVF)は、探索するインデックス走査+距離計算の対象範囲を直接制御するパラメータであり、レイテンシに最も支配的な影響を与える。実際にシングルスレッドで1クエリずつ逐次発行し、p50/p95/p99レイテンシを測定した結果が次の図である(クラスタ構造ありのデータ、hnswlibでnum_threads=1を指定)。

for ef in [10, 50, 100, 200, 400, 800]:
    index.set_ef(ef)
    times = []
    for i in range(NQ):
        t0 = time.perf_counter()
        index.knn_query(queries[i:i+1], k=K, num_threads=1)
        times.append((time.perf_counter() - t0) * 1000)
    times = np.array(times)
    print(ef, times.mean(), np.percentile(times, 50),
          np.percentile(times, 95), np.percentile(times, 99))

図6-2: efSearchとレイテンシ分布(p50/p95/p99)の関係。efSearchを上げるほどp99の裾野(テール)がp50以上の比率で伸びていく様子を示す。

efSearch=10では p50が0.059ms、p99が0.152msだったのに対し、efSearch=800では p50が0.893ms、p99が1.544msまで増加した。p50は約15倍に伸びているのに対しp99はそれ以上の比率で伸びており、efSearchを上げるほど「稀に時間のかかるクエリ」の裾野(テール)が長くなる傾向も観察できる。これは、探索候補が増えるほどグラフ上で訪問するノード数のばらつきも大きくなるためだと考えられる。SLAでp99を保証したい場合、平均レイテンシだけを見てefSearchを決めると痛い目にあう、という実務上の教訓がここから得られる。

バッチ検索とスループット

一方で、多くのANN実装(hnswlibを含む)は複数クエリをまとめて渡すと内部で自動的にマルチスレッド化し、CPUの全コアを使って並列に処理する。第5章のQPS測定は実はこの挙動を利用したものだった。同じefSearch=10の条件で比較すると、シングルスレッド逐次実行では毎秒約16,000件相当(1/0.062ms)だったのに対し、8コアを使ったバッチ処理では毎秒約65,000件に達した。コア数の8倍には届かないものの、バッチ化によって数倍のスループット向上が得られることが確認できる。この差は、スケジューリングやメモリアクセスパターンの効率化(バッチ処理では複数クエリの探索がキャッシュを共有しやすい)によるところが大きい。実運用でスループットを最大化したい場合はクエリをバッチ化してエンジンに渡すこと、逆に単発クエリのレイテンシを最小化したい場合はバッチ化のオーバーヘッド(他クエリの完了を待つ)がむしろ不利に働きうること、の両方を意識する必要がある。

7. ベクトルデータベースはなぜ必要か: RDB・pgvectorとの違い

「ベクトルの列を1つのテーブルのカラムとして持ち、既存のRDBの索引機構で最近傍探索をすればよいのでは」という発想は自然であり、実際にPostgreSQLのpgvectorのような拡張はこのアプローチを取っている。しかし多くの場面でMilvusやOpenSearchのような専用のベクトル検索基盤が選ばれるのには理由がある。

B-treeやGiSTでは何が足りないか

RDBの標準的な索引であるB-treeは、キーに対して全順序(total order)を仮定した1次元的なデータ構造である。範囲検索や等値検索には非常に強いが、「多次元空間での近さ」という順序付け不可能な概念を扱うようには設計されていない。

空間検索向けのGiST(Generalized Search Tree)ベースの索引、たとえばR-treeは多次元のデータを想定して設計されているが、第3章で紹介したWeber・Schek・Blottの研究が示す通り、次元数がおよそ10を超えたあたりから性能が悪化し、単純な逐次スキャンにすら負けるようになる( Weber, Schek, Blott, VLDB 1998 )。埋め込みベクトルは数百〜数千次元が普通であり、この壁は本質的な障害になる。

pgvectorとの違い

pgvectorは実際には伝統的なGiSTを使うのではなく、IVFFlatとHNSWという専用のアクセスメソッドを独自に実装している( pgvector README )。これは「RDBの汎用索引機構をそのまま流用する」のではなく、「RDBの拡張機構(access method API)の中にANN専用のアルゴリズムを実装する」というアプローチであり、専用ベクトル検索エンジンがやっていることの縮小版とも言える。

とはいえ制約は残る。pgvectorのHNSWインデックスはm(デフォルト16)とef_construction(デフォルト64)というHNSWそのもののパラメータを持つが、インデックス全体をトランザクション処理系の中で管理するため、構築には時間がかかる。AWSのブログ記事によれば、pgvector 0.7.0で並列インデックス構築がサポートされる以前は、Auroraでのビルドに大きな時間を要しており、並列化によって最大67倍の高速化が報告されている( AWS Database Blog: Load vector embeddings up to 67x faster with pgvector and Amazon Aurora )。この事実は裏を返せば、素朴なHNSW構築がいかに時間のかかる処理かを物語っている。

ANNインデックスのビルドコストと更新の難しさ

HNSWのようなグラフ型インデックスは、第4章のINSERTアルゴリズムからも分かる通り、1件挿入するたびにグラフを探索して接続を張り直す必要があり、逐次挿入のコストが軽くない。さらに厄介なのが削除である。グラフ構造から1ノードを本当に取り除こうとすると、そのノードを経由していた全ての探索経路(つながっていた近傍リンク)を再接続しなければならず、コストが高い。そのため実務上は、削除対象に墓標(tombstone)を立てて検索結果からは除外しつつ、グラフの物理的な再構築は定期的なコンパクション処理にまとめて任せる、という設計がよく採られる。これは全文検索エンジンにおけるLuceneのセグメント削除(削除フラグを立てて、セグメントマージのタイミングで実際に取り除く)と同じ発想であり、第1章で見た全文検索の知見がベクトル検索にもそのまま活きる部分である。

スケールアウトの必要性

第4章のDiskANNの例が象徴的だが、10億点規模のインデックスを単一ショットで構築しようとすると、ピークメモリが1100GBに達するというケースも報告されている。これは通常のRDBサーバーはおろか、多くの専用マシンの物理メモリすら超える規模である。データ規模がさらに大きくなれば、単一ノードのメモリとディスクに収まりきらなくなるのは時間の問題であり、複数ノードにインデックスを分割して保持し、クエリを並列に投げて結果をマージするスケールアウトの仕組みが必須になる。これはRDBの世界でいうシャーディングに相当する発想だが、ANNインデックス特有の「セグメント同士の結果をどうマージしてトップkを再構成するか」という問題(第6章の結果マージ)が追加で発生する。この必要性こそが、MilvusやOpenSearch(のk-NNプラグイン)のような、分散アーキテクチャを前提に設計された専用のベクトル検索基盤が生まれた最大の理由の1つである。

8. ANN性能を支配する5つの共通原理

ここまで見てきたHNSW・IVF・PQ・DiskANNという個別のアルゴリズムの違いを一度脇に置き、どのエンジンにも共通して現れる原理を5つに抽出しておく。これらは、この後Milvus・OpenSearchという具体的な実装を学ぶ際に、個々の設定項目やAPIの背後にある「なぜそうなっているか」を理解するための共通言語になる。

(1) 候補数パラメータがrecallとレイテンシを同時に動かす。 HNSWのefSearch、IVFのnprobeという名前は違えど、「探索する候補の数を増やせばrecallは上がるが、その分レイテンシとCPUコストも増える」という構造は共通している(第4〜6章)。MilvusでもOpenSearchでも、検索クエリのたびに指定するこの手のパラメータこそが、そのシステムのチューニングの主戦場になる。

(2) インデックスはセグメント単位で持ちマージ・コンパクションが走る。 第1章で見たLuceneの転置インデックスも、第7章で見たHNSWの削除も、共通して「データを小さな単位(セグメント)に分けて持ち、書き込みは新しいセグメントとして追加し、削除は墓標を立てるだけにしておき、バックグラウンドで定期的にセグメントをマージ・再構築する」というアーキテクチャを採用している。これは書き込みスループットと検索性能の両立のための実務的な妥協であり、Milvusのセグメント、OpenSearch(Lucene)のセグメントという言葉が出てきたら、この原理を思い出すとよい。

(3) メモリ階層(RAM/SSD)がアルゴリズム選択を決める。 HNSWやIVFFlatは基本的に全データをRAMに載せる設計であり、高速だがメモリコストが高い。DiskANNはこの制約を破るために、圧縮ベクトルだけをRAMに置きフルデータとグラフをSSDに置くという設計を選んだ(第4章)。どのエンジンを使うにせよ、「今のデータ規模はRAMに収まるのか、収まらないなら圧縮するのかSSDに逃がすのか」という問いは避けて通れない。

(4) フィルタとANNの合成は難しい。 実務では「特定のカテゴリに属する商品だけの中から類似検索したい」のように、メタデータによる絞り込み(フィルタ)とベクトル検索を組み合わせたい場面が非常に多い。素朴には、ANNで上位k件を取ってからフィルタをかける事後フィルタリング(post-filtering)と、フィルタを満たす候補だけを先に絞ってから探索する事前フィルタリング(pre-filtering)の2通りが考えられるが、前者はフィルタ後に結果が足りなくなるリスクがあり、後者はANNインデックスの構造(グラフやクラスタ)がフィルタ条件を考慮していないために効率的に絞り込めないという問題がある。この「フィルタ付きANN」は研究テーマとしても活発で、たとえばVamanaグラフを拡張したFiltered-DiskANNのような専用アルゴリズムも提案されている( Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters )。MilvusとOpenSearchがこの問題にどう対処しているかは、 Milvus内部構造編 ・ OpenSearch内部構造編 でそれぞれ具体的に見ていく。

(5) 削除・更新は再構築で償却する。 第7章で見た通り、グラフ型・空間分割型を問わず、ANNインデックスからの物理的な削除は高コストである。そのため実運用ではまず論理削除(墓標)で検索結果から除外し、コストの高い物理的な再構築(コンパクション)は非同期かつバッチ的にまとめて実行することで、個々の削除・更新操作のレイテンシを低く保つ、という設計が共通して採用される。

以上の5原理は、MilvusとOpenSearchという具体的な実装を学ぶ際の地図になる。 Milvus内部構造編 では、これらの原理がMilvusの具体的なアーキテクチャ(セグメント、Growing/Sealed、DataNode/QueryNodeといったコンポーネント分割)にどう落とし込まれているかを見ていく。 OpenSearch内部構造編 では、既存のLucene/Elasticsearchのセグメントアーキテクチャの上にk-NNプラグインとしてANNがどう統合されているかを見ていく。同じ原理が異なる実装判断としてどう現れるかを比較しながら読み進めてほしい。

第1〜8章のまとめ

ここまでの第1〜8章の要点を1章1行で整理すると次の通りである。

9. ベクトル検索のベンチマークとPoC設計: recallを揃えて比較する

ベンチマークで最もよくある誤りは「recallを揃えずにQPSだけを比較する」ことである。efSearchやnprobeを絞ればどんなインデックスもQPSは上がるが、recallが50%まで落ちていれば実用に耐えない。本章では、公平なPoCを設計するための方法論と、本番運用に入ってからもrecallとレイテンシを保証し続けるための観測設計を扱う。

同一データセット・同一recallターゲットで比較する

比較対象システムには必ず同じデータセット、同じクエリセット、同じ距離関数を使う。その上で、両者のパラメータ(efSearch/efConstruction、nprobe、HNSWのM等)を掃引し、recall-QPSカーブを描く。そして「recall@10 = 0.95」のような固定recallラインを引き、そのライン上でのQPSやレイテンシを比較する。これがann-benchmarksが採用している基本手法であり、「Recall(平均で真の近傍が見つかった割合)をQueries per secondに対してプロットする」ことで初めてインデックス同士の速度比較が意味を持つ( ANN-Benchmarks )。recallを揃えずにQPSだけを比べる比較は、片方が手を抜いているだけの可能性を排除できない。この「recallを揃える」という作法が具体的にどういうことかを図9-1に概念図として示す。

図9-1: 概念図(数式で生成した仮想データ)。recall-QPS平面上で2つのトレードオフ曲線は交差しうるため、recall@10=0.95のような同一ラインの上で比較して初めて公平になる。片方だけrecallを落としてQPSを稼ぐ比較(×印)は無効である。

ウォームアップとキャッシュ状態の統制

OpenSearchのグラフはオフヒープキャッシュに遅延ロードされ、初回クエリは数秒かかることがあるため、warmup APIを実行してからでないと初回クエリの重さがそのまま測定値に混入する( Approximate k-NN search )。Milvusでもコレクションのロード直後はセグメントやインデックスファイルがmmap経由で遅延読み込みされるため、本計測前に捨てクエリを流してキャッシュを温める必要がある。ウォームアップの有無を揃えない比較は、片方だけコールドスタートのペナルティを負わされている可能性がある。

インデックスビルド時間と検索性能の分離

インデックス構築時間(スループット、CPU/メモリ消費)と検索時のレイテンシ/recallは別々の軸で評価する。ビルドが速くても検索が遅いインデックス、あるいはその逆もあり得るため、両者を一つの数値に混ぜて「総合スコア」を作ると意思決定を誤らせる。特にOpenSearchのようにセグメントのマージが発生するシステムでは、「定常状態(steady state)」のビルド性能と「継続的な書き込みが続く中での」ビルド性能を分けて計測する必要がある。

クライアント側ボトルネックの排除

PoCでQPSが頭打ちになったとき、原因がサーバー側ではなくクライアント側(シングルスレッドでの逐次リクエスト、gRPC/HTTPのコネクションプール枯渇、ネットワークのラウンドトリップ)であることは非常に多い。並列度を上げてスループットが線形に伸びるか確認し、クライアントのCPU使用率も監視する。VectorDBBenchは同時実行数を段階的に増やして最大QPSを探索する手法を取っており、この種の外形的なクライアントボトルネックの影響を減らす設計になっている( VDBBench 1.0 )。ただし、QPS_maxは複数の同時実行数を掃引して得られる値であるのに対し、レイテンシは単一クライアントによる直列実行から得られる値であるため、両者を安易に対応付けて解釈してはならない点には注意が必要である。

VectorDBBenchとann-benchmarksの使い方と限界

VectorDBBenchはZillizが公開するOSSベンチマークツールで、Milvus/Zilliz Cloudだけでなく他の主要なベクトルDB/検索エンジンもプラガブルに計測できるよう設計されている( GitHub: zilliztech/VectorDBBench )。recallとQPSを対で報告する設計思想は評価できる一方、開発元がMilvusベンダーであることのバイアス(第10章で後述)を踏まえ、パラメータ選択やハードウェア構成が中立かどうかは利用者自身が確認すべきである。ann-benchmarksはerikbernらが開発した学術寄りのフレームワークで、様々なアルゴリズムをDockerコンテナ化し、複数の代表的データセットに対してrecall-QPSカーブを比較する標準的な土俵を提供する( ANN-Benchmarks )。ただし、いずれのツールもフィルタ付き検索・ハイブリッド検索・実運用に近い書き込み継続下での挙動までは十分にカバーしておらず、あくまで「素のANN性能」の一次スクリーニングとして位置づけ、最終判断は自社データセットでのPoCに委ねるべきである。

PoCチェックリスト

• データセットとクエリセット、正解集合(ground truth top-K)を固定し、両システムで完全に同一のものを使う
• 比較の基準を「同一recallターゲット」に固定し、そのライン上のQPS/レイテンシを比較する
• ウォームアップ手順を明文化し、両システムに同一の手順を適用する
• ビルド時間と検索性能を別のグラフ・別の指標として報告する
• クライアントの並列度を掃引し、QPSが頭打ちになる原因がサーバー側かクライアント側かを切り分ける
• フィルタ付き検索を含める場合は、選択率(何%が残るか)を明記し、選択率ごとの性能を報告する
• 継続的な書き込み(insert/delete)がある状態での検索性能も別途計測する(定常状態だけでなく)
• ハードウェア構成(CPU/メモリ/ディスク種別)とソフトウェアバージョンを明記する
• ベンダー発のベンチマークツールを使う場合は、開発元のバイアスを踏まえてパラメータ設定の妥当性を自分で検証する

PoCの段階で公平に測定できたとしても、本番運用に入った後にrecallが静かに劣化していくのはよくある落とし穴である。ANNインデックスは「正しく動いているように見えて実は劣化している」状態になりやすい。索引パラメータやハードウェアが変わらなくても、削除の蓄積・データドリフト・レプリカ間のリバランスによってrecallは静かに下がる。以下では、本番運用で最低限押さえておくべき観測設計の要点を確認する。

レイテンシ分位点とrecallの定期サンプリング

QPSやp50だけを監視するのは不十分である。ANN検索はrecallとレイテンシのトレードオフの上に成り立っているため、p95/p99レイテンシとrecallは必ずセットで追跡しなければならない。recallは本番トラフィックからは直接測定できないため、正解集合(ブルートフォースで計算したtop-K)をあらかじめ用意したゴールデンクエリセットに対して、日次・週次などの定期ジョブでオフライン測定し、時系列で追う運用が現実的である。これを怠ると、インデックスパラメータ変更やデータ量増加によるrecall劣化を「レイテンシは正常だから問題なし」と誤認したまま放置することになる。

recallは監視しないと静かに劣化する

recallが劣化する典型的な原因は三つある。第一にデータドリフトで、埋め込みモデルが変わらなくても実データの分布が変化すると、HNSWのグラフ構造が最適でなくなり同じefSearchでもrecallが下がる。第二に削除の蓄積で、論理削除されたベクトルがインデックスから物理的に取り除かれるまで(compaction/merge)、探索空間に「ゴースト」が残り実効recallを圧迫する。第三にオートスケールやレプリカ再配置に伴うインデックス再構築中の一時的なrecall低下である。いずれもレイテンシメトリクスには現れないため、ゴールデンクエリセットによる定期recall測定をSLOの一部として組み込む必要がある。

SLO設計の例

実務的なSLOの一例を示す。「p95検索レイテンシ200ms以下」「recall@10が週次サンプリングで0.95を下回らない」「k-NNサーキットブレーカーの発火回数が1時間あたり0件」「compaction/mergeの遅延が1時間以内」といった具体的な数値目標を組み合わせ、レイテンシとrecallを必ずペアで扱うことが、ANNシステム特有のSLO設計の要点である。

10. MilvusとOpenSearchの比較: どちらを選ぶべきか

ここまでの章でANNの原理を一通り押さえた読者にとって、次の関心は自然に「実装としてMilvusとOpenSearchのどちらを選ぶべきか」に向かうはずである。結論を先に言えば、「どちらが速いか」という問いそのものがあまり生産的ではない。両者は同じHNSWやIVFというアルゴリズムを実装していても、「ベクトル検索を専業とする分散システム」と「全文検索エンジンにベクトル検索を後付けしたプラグイン」という、根本的に異なる出自を持つ。この出自の違いが、鮮度・一貫性・運用性のあらゆる設計判断に影を落としている。本章ではベンチマーク数値ではなく、公式ドキュメントに基づく構造的な差分を軸に両者を比較する。それぞれの内部構造——書き込み経路とconsistency制御、segment lifecycle、性能障害の切り分け方など——の詳細は、続く Milvus内部構造編 ・ OpenSearch内部構造編 に譲る。

アーキテクチャの出自の違い

Milvus(2.6系)は、アクセス層(ステートレスなProxy群)・コーディネータ層・ワーカーノード層(Query Node/Data Node/Streaming Node)・ストレージ層(etcd/オブジェクトストレージ/WALサービス)に分離された、ストレージとコンピュートを分離した専用の分散システムである。2.6ではWAL層にPulsar/Kafkaに加えて内製のWoodpeckerも選択可能になり、ストリーミングノードが growing データのクエリと sealed 化を担うようになった( Milvus Architecture Overview )。

対するOpenSearchのk-NNプラグインは、Luceneのセグメントというデータモデルの上にベクトル検索機能を「プラグインとして」載せている。JNI経由でFaiss(C++)やLuceneネイティブのHNSW実装を呼び出す構成であり、ベクトルインデックスはLuceneセグメントに対して1対1で構築される( JNI libraries 、 Approximate k-NN search )。つまりOpenSearchを選ぶことは、実質的に「既存のOpenSearch/Elasticsearchクラスタ運用ノウハウをそのままベクトル検索に転用する」ことを意味し、Milvusを選ぶことは「ベクトル検索専用の新しい分散システムを一つ増やす」ことを意味する。

比較表

どちらが向くかの判断フレーム

判断は「既存資産」「鮮度要件」「フィルタ選択率」「運用チームのスキルセット」の4軸で行うのが実務的である。第一に、既にOpenSearch/Elasticsearchでログや全文検索基盤を運用しているなら、その資産の上にベクトル検索を足すのは統合コストが低い。Amplitudeの事例(後述)はまさにこの理由でOpenSearchを選んでいる。第二に、書き込み直後の可視化を厳密に制御したい(強い一貫性が必要、または逆に速度優先で緩めたい)場合はMilvusのtunable consistencyが表現力で勝る。第三に、フィルタの選択率が極端に低い(ほぼ全件除外)ようなワークロードでは、両者とも自動的にexact searchへフォールバックする仕組みを持つが、その閾値の挙動を検証すべきである。第四に、専任のインフラチームがKubernetes運用に慣れているかどうかは、Milvusの運用負荷を大きく左右する。この4軸を順に辿る判断フローを図10-1に整理した。

図10-1: 「既存資産」「鮮度・一貫性要件」「フィルタ選択率」「運用チームのスキルセット」の4軸を上から順に確認し、OpenSearch有力/Milvus有力/PoCで比較のいずれかに至る判断フロー。

公平性についての注記

VectorDBBenchやZillizブログのベンチマークはMilvus開発元であるZillizが公開しているものであり、パラメータチューニングやハードウェア選定がMilvusに有利な条件になりがちな構造的バイアスを内包する( VectorDBBench )。同様にAWSやOpenSearchプロジェクトが発信する事例・ベンチマークも自社サービスの成功事例として選別されている可能性がある。本記事はどちらのベンダーブログの数値も鵜呑みにせず、公式ドキュメントに記載された「仕様」レベルの事実(サポートするインデックス種別、一貫性モデル、APIの挙動)を比較の基盤とし、性能主張は第9章のPoC方法論で自分自身のデータに対して検証することを推奨する。

事例横断で見える共通点

Milvus側の事例(Tokopedia、Shopeeなど)とOpenSearch側の事例(Amplitude、MANZ、Juiceboxなど)を横断して見えてくる共通点は3つある。第一に「PoCで複数候補を比較してから決める」姿勢である。第二に「既存の運用資産・チームスキルに合わせた選択」であり、OpenSearchを選んだ事例はいずれも既存のAWS/OpenSearch運用体制の延長線上にある。第三に「本番投入後もバージョンアップグレードは慎重に検討する」現実である。ベンチマーク上の数値差よりも、こうした組織的・運用的な制約が実際の選定を左右していることが、これらの一次情報から読み取れる。各事例の詳しい経緯——PoCの進め方、移行の経緯、定量的な改善効果——は、 Milvus内部構造編 ・ OpenSearch内部構造編 でそれぞれ紹介する。

11. まとめ

本記事(基礎編)の内容を10項目に凝縮する。

1. ANN(近似最近傍探索)は「厳密解を諦める代わりに探索空間を絞り、高次元の呪いを回避する」という一つの原理から出発している。
2. 木構造(kd-tree)は低次元では有効だが、高次元では実質的に全件探索に近づく。これがLSHやグラフ・量子化ベースの手法が発展した動機である。
3. LSHは理論保証を持つが、実データでの精度と速度は後発のグラフ・量子化手法に劣後することが多く、現在の主流ではない。
4. 積量子化(PQ)はベクトルを部分空間に分割して符号化することでメモリを桁違いに圧縮する、量子化系の基礎技術である。
5. HNSWはNSWの階層化により対数的な探索を実現し、現在最も広く使われるグラフベースANNアルゴリズムとなった。MilvusのHNSWインデックスもOpenSearchのFaiss/Lucene HNSWも、この一つの論文に起源を持つ。
6. DiskANN/SPANNはメモリに乗り切らない規模のデータを、SSDやディスクとメモリのハイブリッド構成で扱うために発展した系譜である。
7. RaBitQのような理論保証付き量子化やGPU向けグラフ構築(CAGRA)は、2023年以降の直近のフロンティアであり、MilvusはRaBitQを2.6で、OpenSearchはGPUインデックスビルドを3.0以降(プレビュー)でそれぞれ取り込んでいる。
8. Milvusは「ベクトル検索専用の分散システム」、OpenSearchは「全文検索エンジンにベクトル検索を統合したシステム」という出自の違いが、鮮度・一貫性・運用性の設計思想の違いに直結する。
9. ベンチマーク数値は文脈(recallを揃えているか、ウォームアップしたか、誰が発表しているか)を抜きに比較できない。「速い/遅い」という結論だけを持ち帰るのは危険である。
10. 本番運用ではrecallは放っておくと静かに劣化する。レイテンシだけでなくrecallを定期的にサンプリング測定し、SLOに組み込むことが必須である。

これらすべてを貫く一つのメッセージがある。ANNの原理を体系的に理解していれば、MilvusもOpenSearchも「同じ原理(近似・量子化・グラフ探索・分散処理)の別の実装」として読める。ベンダーのAPIドキュメントを暗記するのではなく、背後にあるアルゴリズムとトレードオフを理解していれば、次に登場する新しいベクトルDBや検索エンジンも、既知の原理の組み合わせとして素早く咀嚼できるはずである。

学習ロードマップ

さらに深く学びたい読者には、以下の順序を勧める。まずhnswlibやfaissのソースコードを実際に読み、HNSWのef/Mパラメータが探索グラフの形にどう影響するかを手元のデータで実験する。次にDiskANN論文とその公式実装(Microsoft Research)を読み、メモリとディスクのハイブリッド構成の設計判断を追う。並行して、MilvusとOpenSearchそれぞれの公式ドキュメントの「チューニングガイド」を通読し、本記事で扱った各パラメータが実際の設定項目としてどう表現されているかを確認する。最後に、自社のデータセットを使ってVectorDBBenchやann-benchmarksを実際に動かし、第9章のチェックリストに沿って自分の手でrecall-QPSカーブを描いてみることが、最も確実な理解の定着方法である。

ここまでが基礎編の内容である。次の2本では、ここで押さえた原理をMilvusとOpenSearchという具体的な実装がどう組み込んでいるかを見ていく。 Milvus内部構造編 では、Proxy/Coordinator/QueryNode/DataNode/StreamingNodeへの層分割、書き込み経路とtunable consistencyの制御、segment lifecycleを掘り下げる。 OpenSearch内部構造編 では、Luceneのセグメントモデルの上にk-NNプラグインがどう統合されているか、warmupやexact fallback、native memoryの管理を掘り下げる。原理を知っていれば、この2本もまた「同じ原理の別実装」として読み進められるはずである。

よくある質問(FAQ)

Q. ANNとk-NN(厳密探索)の違いは何ですか?

k-NN(厳密探索、brute-force)はクエリと全データ点との距離を計算し尽くして真の最近傍を求める方式で、データ点数を\(N\) 、次元数を\(d\) とすると距離計算に\(O(N \cdot d)\) かかる。データ規模が数百万〜数十億になるとこの線形コストとcurse of dimensionalityが重なり実用的なレイテンシを維持できなくなるため、真の最近傍を保証する代わりに高い確率でそれに近い集合をずっと少ない計算量で返すANN(近似最近傍探索)が使われる。詳細は第3章。

Q. HNSWとIVFはどちらを選ぶべきですか?

一概にどちらが優れているとは言えず、精度(recall)・速度・メモリ/ディスクという3つの軸のどこを優先するかで決まる。HNSWはベクトル本体とグラフ接続情報を全てRAMに保持するためrecallと速度は高いがメモリ効率は良くなく、IVFは走査対象をnprobe個のセルに絞ることで計算量を抑えつつ、グラフ接続情報を持たない分メモリはやや軽い。実務ではIVFとPQを組み合わせたIVFPQのように、複数の型を組み合わせて使うことも多い。詳細は第4章。

Q. recall(再現率)はどのくらいを目指すべきですか?

万能の正解値は存在しない。recallと速度(QPS)はトレードオフの関係にあり、候補数パラメータ(HNSWのefSearch、IVFのnprobeなど)を振りながらrecallとQPSを同時に測定するrecall-QPSトレードオフ曲線を、自分のデータセットで実際に描いて判断する必要がある。データの分布(一様ランダムか、意味的なクラスタ構造を持つか)によって同じrecallに到達するためのコストも大きく変わるため、公開ベンチマークの数値をそのまま流用せず、同一recallターゲット上でシステムを比較するのが公平な作法である。詳細は第5章・第9章。

Q. pgvectorではなく専用のベクトルデータベースが必要になるのはどんなときですか?

pgvectorはIVFFlatやHNSWといった専用のアクセスメソッドを実装しており小〜中規模のワークロードでは有効な選択肢だが、インデックス全体をトランザクション処理系の中で管理するため構築に時間がかかりやすく、グラフ型インデックスの逐次挿入・削除のコストも軽くない。データ規模が数億〜数十億点に達し単一ノードのメモリ・ディスクに収まりきらなくなると、複数ノードにインデックスを分割してクエリを並列に投げ結果をマージするスケールアウトの仕組みが必須になり、これがMilvusやOpenSearchのような分散アーキテクチャを前提にした専用ベクトル検索基盤が選ばれる最大の理由になる。詳細は第7章。

Q. MilvusとOpenSearchはどちらが速いですか?

単純な速度比較にはあまり意味がない。両者は同じHNSWやIVFというアルゴリズムを実装していても「ベクトル検索専業の分散システム」と「全文検索エンジンにベクトル検索を後付けしたプラグイン」という異なる出自を持ち、鮮度・一貫性・運用性の設計が根本的に異なるため、recallを揃えないベンチマーク数値を鵜呑みにするのは危険である。判断すべきは「どちらが速いか」ではなく「既存資産・鮮度要件・フィルタ選択率・運用チームのスキルセット」に照らしてどちらが向くかであり、最終的にはrecallを揃えた自分自身のデータでのPoCで確かめるべきだ。それぞれの内部構造の詳細は Milvus内部構造編 と OpenSearch内部構造編 を参照してほしい。詳細は第9章・第10章。

関連書籍

本シリーズの内容を書籍でも体系的に学びたい読者には、日本語で書かれたベクトル検索の実践的な入門書として次の一冊を挙げておく。

他の分野の定番書は エンジニアにおすすめの技術書10選 にまとめている。

付録A: 論文でたどる ANN の発展史

付録B: 用語集

本記事で登場する主要用語を「基礎」「評価・運用」の2カテゴリでまとめる。各項目の定義は本文の該当章の記述に基づく。Milvus・OpenSearch固有の用語(growing/sealed segment、tunable consistency、native memory、on_disk modeなど)は、 Milvus内部構造編 ・ OpenSearch内部構造編 それぞれの巻末用語集を参照してほしい。

基礎

• ANN(Approximate Nearest Neighbor, 近似最近傍探索): 真の最近傍を保証する代わりに、高い確率でそれに近い集合を、厳密探索よりずっと少ない計算量で返す近似解法。curse of dimensionalityとbrute-forceの線形計算量という2つの制約から必然的に要請される(第3章)。
• recall(再現率): recall@kは、ANNが返した上位k件のうちbrute-forceで求めた真の上位k件と一致する割合。クエリごとに計算し平均したものが一般に報告される値(第3章)。
• curse of dimensionality(次元の呪い): 次元数が増えるにつれ、任意の点から見た最近傍と最遠点の距離差が0に収束し、「近傍」という概念自体が意味を失っていく現象。木構造索引が高次元で単純な逐次スキャンに計算量で追い抜かれる一因になる(第3章)。
• recall-QPSトレードオフ曲線: 候補数パラメータ(efSearch、nprobe等)を振りながらrecallとQPSを同時に測定し両者の関係を描いた曲線。右上(高recallかつ高QPS)にあるほど優れた実装とされる(第5章、第9章)。
• HNSW(Hierarchical Navigable Small World): NSWに階層構造を導入したグラフ型ANNアルゴリズム。上位層で大まかに絞り込み、階層を降りるごとに探索を精密化する(Malkov & Yashunin, 2016)。MilvusのHNSWインデックスもOpenSearchのFaiss/Lucene HNSWも、この一つの論文に起源を持つ(第4章)。
• efSearch: HNSWの検索時に保持する動的候補リストのサイズ。大きいほどrecallが上がるがレイテンシも増える(第4章)。OpenSearchのLuceneエンジンはこのパラメータの扱いが異なる(詳細は OpenSearch内部構造編 )。
• IVF(Inverted File index): k-meansなどでベクトル空間をnlist個のクラスタに分割し、クエリに近いnprobe個のクラスタだけを走査する空間分割型ANN(第4章)。
• nprobe: IVF検索時に走査するクラスタ数。増やすほどrecallは上がるが計算量も増える(第4章)。
• PQ(Product Quantization, 積量子化): ベクトルをM個のサブベクトルに分割し、各サブ空間ごとに学習したコードブックのセントロイド番号に置き換えて圧縮する量子化手法(Jégou, Douze, Schmid, 2011)。メモリ使用量を桁違いに削減できる代わりにrecallの上限が下がる(第4章)。
• ADC(Asymmetric Distance Computation, 非対称距離計算): PQ検索時にクエリベクトル自体は量子化せず生のまま保持し、サブ空間ごとの距離ルックアップテーブルを使ってデータベース側の量子化ベクトルとの距離を近似計算する方式(第4章)。
• quantization(量子化): ベクトルをより少ないビット数で近似表現し、メモリ使用量と距離計算コストを削減する技術の総称。PQ・SQ(スカラー量子化)・バイナリ量子化などが含まれる(第4章。各エンジンでの量子化の扱いは Milvus内部構造編 ・ OpenSearch内部構造編 で扱う)。
• DiskANN: フルサイズのベクトルとグラフをSSD上に置き、PQで圧縮したベクトルのみをRAMにキャッシュすることで、コモディティなRAM量でも十億点規模の高recallな近似探索を実現するシステム(Subramanya et al., 2019、第4章)。
• Vamana: DiskANNの中核となるグラフ構築アルゴリズム。貪欲探索GreedySearchと、距離しきい値パラメータαによって長距離エッジを意図的に残す枝刈りアルゴリズムRobustPruneから成る(第4章)。
• RRF(Reciprocal Rank Fusion): 複数の検索結果リストを、生スコアではなく順位だけを使って統合するランキング統合手法(Cormack et al., 2009)。全文検索とベクトル検索という性質の異なるスコアを混ぜるハイブリッド検索の標準的な手法になっている(第1章)。
• ハイブリッド検索(hybrid search): 全文検索(BM25)とベクトル検索を組み合わせ、両者のスコアを1つのランキングに統合する検索方式。Milvusは2.5からBM25ネイティブ対応、OpenSearchはnormalization-processorでスコアを統合する(第1章、第10章)。
• セグメント(segment): インデックスを構成する管理単位。Milvusでは書き込み中のgrowing segmentと確定済みのsealed segmentに分かれ、OpenSearch(Lucene)では不変のセグメント単位でHNSWグラフが個別に構築される、というように製品ごとに意味合いが異なる(詳細は Milvus内部構造編 ・ OpenSearch内部構造編 )。

評価・運用

• QPS(Queries Per Second): 単位時間あたりに処理できるクエリ数を表すスループット指標(第5章)。
• レイテンシのp95/p99: レイテンシ分布のパーセンタイル値。単純平均と異なり「95%(99%)のクエリはこの時間以内に返る」という、SLAやSLOの議論で実務的な意味を持つ指標(第5章、第9章)。
• VectorDBBench: Zillizが公開するOSSベンチマークツール。Milvus/Zilliz Cloudに限らず主要なベクトルDB/検索エンジンをプラガブルに計測できるが、開発元がMilvusベンダーであることに由来するバイアスに注意が必要である(第9章、第10章)。
• ann-benchmarks: erikbernらが開発した学術寄りのベンチマークフレームワーク。複数のアルゴリズムをDocker化し、代表的データセットに対してrecall-QPSカーブを比較する標準的な土俵を提供する(第9章)。
• SLO(Service Level Objective): 本記事の文脈では「p95レイテンシ200ms以下」「recall@10が週次サンプリングで0.95を下回らない」のように、レイテンシとrecallを必ずペアで扱う運用目標の設計を指す(第9章)。

付録C: 主要参照先

論文

• Jon Louis Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM, 18(9), 1975. https://dl.acm.org/doi/10.1145/361002.361007
• Piotr Indyk, Rajeev Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” STOC 1998. https://dl.acm.org/doi/10.1145/276698.276876
• Mayur Datar et al., “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” SoCG 2004. https://dl.acm.org/doi/10.1145/997817.997857
• Hervé Jégou, Matthijs Douze, Cordelia Schmid, “Product Quantization for Nearest Neighbor Search,” IEEE TPAMI, 33(1), 2011. https://ieeexplore.ieee.org/document/5432202
• Yury Malkov et al., “Approximate Nearest Neighbor Algorithm Based on Navigable Small World Graphs,” Information Systems, 45, 2014. https://www.sciencedirect.com/science/article/pii/S0306437913001300
• Yu. A. Malkov, D. A. Yashunin, “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.” https://arxiv.org/abs/1603.09320
• Jeff Johnson, Matthijs Douze, Hervé Jégou, “Billion-Scale Similarity Search with GPUs.” https://arxiv.org/abs/1702.08734
• Suhas Jayaram Subramanya et al., “DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node,” NeurIPS 2019. https://www.microsoft.com/en-us/research/publication/diskann-fast-accurate-billion-point-nearest-neighbor-search-on-a-single-node/
• Ruiqi Guo et al., “Accelerating Large-Scale Inference with Anisotropic Vector Quantization,” ICML 2020. https://arxiv.org/abs/1908.10396
• Qi Chen et al., “SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search,” NeurIPS 2021. https://arxiv.org/abs/2111.08566
• Hiroyuki Ootomo et al., “CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs.” https://arxiv.org/abs/2308.15136
• Jianyang Gao, Cheng Long, “RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search.” https://arxiv.org/abs/2405.12497
• Kevin Beyer et al., “When Is ‘Nearest Neighbor’ Meaningful?,” ICDT 1999. https://members.loria.fr/MOBerger/Enseignement/Master2/Exposes/beyer.pdf
• Roger Weber, Hans-Jörg Schek, Stephen Blott, “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces,” VLDB 1998. https://www.vldb.org/conf/1998/p194.pdf
• Gordon V. Cormack, Charles L. A. Clarke, Stefan Büttcher, “Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods,” SIGIR 2009. https://dl.acm.org/doi/10.1145/1571941.1572114
• Siddharth Gollapudi et al., “Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters,” WWW 2023. https://dl.acm.org/doi/10.1145/3543507.3583552
• Jianguo Wang et al., “Milvus: A Purpose-Built Vector Data Management System,” SIGMOD 2021. https://www.cs.purdue.edu/homes/csjgwang/pubs/SIGMOD21_Milvus.pdf
• Rentong Guo et al., “Manu: A Cloud Native Vector Database Management System,” VLDB 2022 (PVLDB 15(12)). https://www.vldb.org/pvldb/vol15/p3548-yan.pdf

ベンチマーク

• ANN-Benchmarks: https://ann-benchmarks.com/index.html
• VectorDBBench (GitHub): https://github.com/zilliztech/VectorDBBench
• VDBBench 1.0 (Zilliz blog): https://zilliz.com/blog/vdbbench-1-0-benchmarking-with-your-real-world-production-workloads

実装コード

• Faiss (Meta): https://github.com/facebookresearch/faiss
• hnswlib: https://github.com/nmslib/hnswlib
• Milvus: https://github.com/milvus-io/milvus
• Knowhere(Milvusのインデックス実行エンジン): https://github.com/zilliztech/knowhere
• OpenSearch k-NN plugin: https://github.com/opensearch-project/k-NN
• google-research/scann: https://github.com/google-research/google-research/tree/master/scann

Milvus公式(代表)

• Milvus Architecture Overview: https://milvus.io/docs/architecture_overview.md
• In-memory Index: https://milvus.io/docs/index.md

OpenSearch公式(代表)

• Approximate k-NN search: https://docs.opensearch.org/latest/vector-search/vector-search-techniques/approximate-knn/
• Methods and engines: https://docs.opensearch.org/latest/mappings/supported-field-types/knn-methods-engines/

Milvus・OpenSearchそれぞれのより詳細な公式ドキュメントリンク(consistency、segment lifecycle、native memory、on_disk mode等)は、 Milvus内部構造編 ・ OpenSearch内部構造編 の巻末にまとめてある。