アーカイブ / RAG
500億件のベクトルを一つの論理グラフで検索するDistributedANN
DistributedANN
DistributedANNの原論文から掲載した図です。細部はクリックして拡大できます。
原論文の図の説明を読む
Figure 2: A visual depiction of the unified graph construction process. Partitions are represented by colored regions, and neighborhoods by dark shading. When points exist in multiple partitions, their neighborhoods will be merged by taking the union of neighbor lists, yielding a unified graph.
概要
- 分散した保存先に約500億件のベクトルを一つの論理グラフとして置き、先頭索引と保存先での距離計算を使って検索する。
- 著者らの3複製での比較では、Recall@5は90.8％対83.0％、処理量は毎秒10万件超対約1万5000件だった。
- 同じ比較で中央値待ち時間は26対16ミリ秒、SSD使用量は780対270 TiBと増えた。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、DistributedANNの仕組み
- 01質問ベクトル
- 02先頭索引で出発点取得
- 03分散ノードで距離計算
- 04候補を更新して結果返却
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
DistributedANNは、大量のベクトルから質問に近い項目を探す分散検索サービスである。ベクトルは対象を数値の並びで表したもので、近似最近傍探索は全件を厳密に比べる代わりに、近い候補を効率よく探す方法を指す。
大規模な従来方式ではデータを区画に分け、区画ごとに索引を作る。対象が増えると検索に必要な区画と読み取り処理も増えやすい。著者らはBingのウェブ検索で使う規模を対象に、この負担を減らそうとした。
手法
質問をベクトルとして受け取り、まずメモリ上の小さな「先頭索引」で探索の出発点を得る。その後、分散した保存先にあるグラフの隣接ノードを順にたどる。たとえばウェブ検索の質問に近い項目を探す場合、出力は候補の識別子と距離を並べたものになる。
各グラフノードには隣接候補の圧縮ベクトルを複製して持たせる。保存先の機械が、ノード内の元のベクトルと質問との距離、および圧縮された隣接候補の距離を計算し、候補情報を返す。検索をまとめる機能が有望な候補を選び直して指定回数だけ探索する。大きなグラフは、区画別に作ったグラフの共通ノードをつなぎ合わせて構築する。
新規性
著者らの主張する進歩は、約500億件のベクトルを独立した小索引に分けて検索する代わりに、分散した一つの論理グラフとして探索できるようにした点にある。論理グラフとは、保存先が複数でも、検索時にはつながった一つの索引として扱う構造を指す。
圧縮ベクトルを隣接ノードに複製し、探索の出発点をメモリ上の小索引で探す。さらに保存先で距離を計算して結果を返し、ネットワーク越しに運ぶデータ量と探索の往復回数に対応した。
従来手法との違い
比較対象は、ベクトルをクラスタごとに分け、各区画に独立した索引を置く方式である。掲載された実験では、203区画から質問に近い上位40区画を選び、各区画を検索した。区画ごとに読み取り量を割り当てる構成である。
DistributedANNは、区画をまたぐ一つのグラフで候補をたどり、有望な場所へ読み取りを振り向ける。著者らの比較では、検索品質と処理量が高い一方、待ち時間、SSD使用量、メモリ使用量、質問当たりの通信量も増えた。
実験結果
著者らは、Bingの索引の一部に当たる約500億件の384次元int8ベクトルと、抽出したウェブ検索質問を用いた。実運用環境で機械構成をおおむねそろえ、3複製で比較した表では、DistributedANNと区画方式のRecall@5は90.8％対83.0％、Recall@200は71.9％対67.4％だった。Recallは正解を検索結果に含められた割合を示す。
同じ表で中央値待ち時間は26対16ミリ秒、質問当たりの読み取り回数は640対4800、処理量は毎秒10万件超対約1万5000件、SSD使用量は780対270 TiBだった。これらは掲載されたデータと設定での著者らの結果であり、別の文書集合で同じ差が出ることは示していない。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：大量の社内規程・手順書から、社員の質問に関連する文書を探す。利用を許可された文書をベクトル化して索引に入れ、質問のベクトルから候補の文書識別子を返す。担当者が原文を確認して回答を作る運用を想定する。
必要な元データは索引に入れる文書と想定質問で、評価には質問ごとの関連文書ラベルを用意する。文書更新に合わせた索引の作り直しや追加方法は用途に応じて設計する。センサーは不要であり、社内文書での改善は論文では検証されていない。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：利用許可を得た文書と想定質問を集め、同じ方法でベクトル化する。質問ごとに関連文書の正解ラベルを作り、区画別の索引を比較基準として、小規模な検索環境を用意する。元データは文書と質問であり、センサーは不要である。追加学習を試すなら、その学習データは別途定める。
文書の追加・更新を索引へ反映する手順を決め、両方式を同じ条件で測る。確認する値は上位候補のRecall、待ち時間、毎秒の処理件数、読み取り回数、保存容量である。一部ノードの応答が欠けた場合も測り、許容値を満たすか判断する。
限界と課題
著者らは、比較方式より待ち時間とSSD使用量が増えることを報告している。圧縮ベクトルを複数ノードへ複製することが容量増につながり、メモリ上の先頭索引は処理量を増やす際に計算能力の制約になった。高度な分割方式との実測比較も今後の課題としている。
編集上の検証事項は、自組織のデータ量と質問量で容量と応答時間を許容できるか、更新時や一部ノードの応答欠落時に必要な検索品質を保てるかである。正解ラベルの作り方も用途に合わせて定める必要がある。
出典
元のタイトル・要旨を確認する（英語）
DISTRIBUTEDANN: Efficient Scaling of a Single DISKANN Graph Across Thousands of Computers
We present DISTRIBUTEDANN, a distributed vector search service that makes it possible to search over a single 50 billion vector graph index spread across over a thousand machines that offers 26ms median query latency and processes over 100,000 queries per second. This is 6x more efficient than existing partitioning and routing strategies that route the vector query to a subset of partitions in a scale out vector search system. DISTRIBUTEDANN is built using two well-understood components: a distributed key-value store and an in-memory ANN index. DISTRIBUTEDANN has replaced conventional scale-out architectures for serving the Bing search engine, and we share our experience from making this transition.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01