Zenn
🔡

(日本語訳) Vector databases (Part 3): Not all indexes are created equal

2023/09/24に公開
1件
#
vectordb
#
vectorsearch
#
vectordatabase
#
vectorstore
tech

日本語訳： ベクトルデータベース(パート3): すべてのインデックスが同じとは限らない

訳者前書き

ベクトルデータベースについていろいろと調査・検証していたところ、以下の記事を見つけて、内容が非常によくまとまっており、多くの人にとっても有用な記事ではないか感じました。もはや翻訳などはDeepLやChatGPTで簡単にできる時代になりつつありますが、まだまだ検索エンジンで検索されることも多いと思いますし、少しでも参照しやすくなればと考えて、作者であるPrashanth Rao氏に許可を頂いた上で日本語に翻訳したものとなっています。

全4回の記事の第3回目となります。

元記事
https://thedataquarry.com/posts/vector-db-3/

Prashanth Rao氏のGitHubアカウント
https://github.com/prrao87

Prashanth Rao氏のTwitterアカウント
https://twitter.com/tech_optimist

前回の日本語訳はこちら

https://zenn.dev/kun432/articles/20230921-vector-databases-jp-part-2

ベクトルインデックスの整理

ベクトルデータベースに関するシリーズの3回目である。パート1では、様々なDBベンダーの提供内容と、それらがどのように違うのかを高いレベルで比較し、パート2では、ベクトルDBとは何か、そしてベクトルDBが何をするのか、という基本的なことに焦点を当てた。Dmitry Kan氏による「すべてのベクトルデータベースが同じように作られているわけではない」[1]という素晴らしい投稿をすでにご覧になっているかもしれない。この記事では021年当時の市場にある様々なベクトルデータベースの違いを取り上げたものである。それ以後も、状況は絶えず進化しており、各DBはその内部において他とは異なるため、ベクトル検索のバックボーンであるインデックスについて深く掘り下げることは意味があると考えた。

ベクトルデータベースとは何か？が十分に明確になったならば、一旦立ち止まって、何百万、何十億、あるいは何兆ものベクトル[2]の検索を実現するためにどのようにスケーリングしているかを考えてみよう。ベクトルデータベースの主要な目的は、ベクタトルデータタイプが第一級市民であるような方法で、データを高速かつ効率的に保存し、意味的に問い合わせる手段を提供することである。2つのベクトル間の類似性は、コサイン距離やドット積のような距離メトリクスによって測定される。ベクトルデータベースを使う際には、検索アルゴリズムと、近似最近傍（ANN）検索アルゴリズムが動作するベースとなっているインデックスを、明確に区別することが重要である。

ほとんどの状況で、ベクトルインデックスの選択には、精度（適合率/再現率）とスピード/スループットのトレードオフが伴う。文献を精査した結果、ベクトルインデックスの手法は、データ構造と圧縮レベルの2つのレベルで整理できることがわかった。これらの分類は必ずしも網羅的なものではなく、多くの文献が様々なインデックスを整理する正しい方法について意見を異にしているため、これはそれらをすべて理解しようという私の最大限の試みである。それでは始めよう！😅

訳者注

precision/recallについててChatGPTに補足説明させてみました。

レベル1： データ構造

インデックスを構築するために使用されるデータ構造に基づいてインデックスを整理することから始めると良い。これは視覚的に検討するのが最適である。


ベクトルインデックスのベースとなっているデータ構造による分類

ハッシュベースのインデックス

ハッシュベースのインデックス、例えばLSH（Locally Sensitive Hashing）は、元の類似性をできるだけ保持するように、高次元のデータを低次元のハッシュコードに変換する。インデックス作成時に、類似したポイントが衝突する可能性を高めるためにデータセットは複数回ハッシュされる（衝突を最小限に抑えることを目的とした従来のハッシュ技術とは逆）。クエリ時には、クエリポイントもインデックス作成時に使用された同じハッシュ関数を使用してハッシュされ、類似したポイントが同じハッシュバケットに割り当てられるため、検索が非常に高速である。ハッシュベースのインデックスの主な利点は、大量のデータにスケーリングしながら非常に高速であることだが、欠点はそれほど正確ではないことである。

ツリーベースのインデックス

ツリーベースのインデックス構造は、バイナリーサーチツリーを使用してて、高次元空間での高速検索を可能にする。ツリーは、類似したデータポイントが同じサブツリー内に配置されるように構築され、これにより近似的な最近傍を発見するのが非常に高速になる。Spotifyが開発したAnnoy(Approximate Nearest Neighbours Oh Yeah)は、バイナリサーチツリー（二分探索木）を多数組み合わせて「森」として使用する代表的な手法である。ツリーベースのインデックスの欠点は、低次元のデータに対してはそれなりにうまく機能するが、高次元のデータに対してはデータの複雑さを十分に捉えることができないため、あまり正確ではないということである。

訳者注

グラフベースのインデックス

グラフベースのインデックスは、ベクトル空間内のデータ点がグラフを形成するという考えに基づいている。このグラフでは、ノードはデータの値を表し、ノード間をつなぐエッジはデータ点間の類似性を示す。グラフは、類似したデータ点がエッジでつながる確率が高くなるように構築される。そして、ANN検索アルゴリズムは、このグラフを効率的に探索するために設計されている。グラフベースのインデックスの主な利点は、高次元データでの近似的な最近傍の検索が可能であり、メモリ効率も良いことである。HNSWやVamanaはグラフベースのインデックスの代表的な例である。

さらに進んだものとして、グラフベースのインデックスにツリーベースのインデックスの概念を取り入れたものがNGT3[3]（Neighbourhood Graphs and Trees）である。Yahoo!Japanによって開発されたNGTは、インデックス作成時に2つの構築を行う。1つは、密なkNNグラフを双方向グラフに変換するもの、もう1つは、navigatable small world（NSW）グラフをインクリメンタルに構築するものである。純粋なグラフベースのインデックスと異なる点は、グラフ構築時に貪欲検索の変種を使用するツリー状構造（Vantage-point、または「VP」ツリー）を介した範囲検索を使用することである。両方の構築の結果、高い外向きの次数を持つノードが得られる。組み合わせ爆発を避けるために、検索が起源となるシード頂点は、範囲検索を使用して効率的にグラフ内を探索する。これにより、NGTはグラフベースとツリーベースのハイブリッドなインデックスとなる。

転置ファイルインデックス

転置ファイルインデックス（IVF）は、ベクトル空間をテッセレーションされたセル、いわゆるボロノイ図に分割する。これにより、クラスタリングと同様の方法で、検索空間が縮小される。最近傍を見つけるためには、ANNアルゴリズムは、最も近いボロノイセルの中心を特定しそのセル内だけを検索すればよい。IVFの利点は、関心のある類似性の領域を迅速に絞り込むANNアルゴリズムを設計するのに役立つことだが、その原型の欠点は、ベクトル空間をテッセレーションする際の量子化ステップが非常に大量のデータに対して遅くなることである。その結果、IVFは、性能向上のために直積量子化(product quantization: PQ)のような量子化手法と組み合わせるのが一般的である。

レベル2： 圧縮

インデックスを整理するための2つ目のレベルは、その圧縮レベルである。「フラット」または総当たりのインデックスは、ベクトルをそのままの形で保存するものである。クエリベクトルは、データベース内のすべてのベクトルと徹底的に比較される。以下の図は、それを3次元空間に簡略化した例である。本質的に、このようなインデックスを使用することは、kNN検索を行うようなもので、返される結果は、k個の最も近いベクトルとの正確な一致になる。ご想像の通り、結果を返すために必要な時間は、データの大きさとともに線形的に増加するため、数十万ベクトル以上のデータセットに適用するのは非現実的になる。


kNN（網羅的）検索におけるフラットインデックス： Pineconeブログを参考にした図

検索の効率を向上させるための解決策は、検索の正確性をある程度犠牲にして圧縮することである。このプロセスは量子化と呼ばれ、インデックス内のベースとなるベクトルを、少ないバイト数で構成されるチャンクに分割する（通常は浮動小数点数を整数に変換する）。これにより、検索中のメモリ消費と計算コストを削減することができる。

フラットインデックス

ANN（非網羅的）検索を使用する場合、IVFやHNSWのような既存のインデックスは「フラット」と呼ばれ、クエリーベクトルとデータベースベクトル間の距離を生のまま直接計算する。これは量子化されたものと区別するためである。例えば、IVF-Flat、HNSW-Flatなどというような言い方になる。

量子化インデックス

量子化インデックスとは、既存のインデックス（IVF、HNSW、Vamana）と量子化などの圧縮方法を組み合わせて、メモリの使用量を減らし、検索の速度を上げるものである。量子化は通常、スカラー量子化（SQ: Scalar Quantization）または直積量子化（PQ: Product Quantization）の2つのタイプ[4]のいずれかである。SQは、ベクトル内の浮動小数点数を整数（バイト単位でのサイズがはるかに小さい）に変換する。これは各次元の最小値と最大値を考慮して、ベクトルを対称的にビンに分割することで行われる。

PQは、ベクトルの各次元に沿った値の分布を考慮して圧縮とデータ削減[4:1]の両方を行う、より洗練された方法である。PQの背後にある考え方は、大きな次元のベクトル空間を、各部分空間ごとにそれぞれ自身のクラスタに量子化することにより、より小さな次元の部分空間の直積集合に分解することである ー ベクトルは短いコードで表され、ベクトル間の距離はそのコードから効率的に推定されるようになり、これを再生値という。非対称のビンニング手順が使用される（SQとは異なる）ことにより、各部分空間内のベクトルの分布を近似距離の推定の一部として取り入れることで、適合率が向上[5]する。ただし、再現率がかなり大幅に減少する[6]というトレードオフがある。

人気のインデックス

ここまでに挙げたインデックス作成方法のうち、ほとんどのベクトル特化型データベースは、そのうちの数種類しか実装していない。これは非常に急速に進化している分野であり🔥、あなたがこれを読んでいる時点でここに書かれている多くの情報は古くなっているかもしれない。興味のあるデータベースがどのようなインデックスをサポートしているか、については、最新のドキュメントをチェックすることを強く推奨する。このセクションでは、複数のベンダーが注目している、人気のある、そしてこれから登場するインデックスに焦点を当てていこう。

IVF-PQ

IVF-PQは、MilvusやLanceDBのようなデータベースで利用可能な複合インデックスである。インデックスのIVF部分は検索空間を絞り込むために使用され、PQ部分はクエリベクトルとデータベースベクトルとの間の距離計算を高速化し、ベクトルを量子化することでメモリ要件を削減するために使用される。この2つを組み合わせる最大の利点は、PQコンポーネントによって速度が大幅に向上し、IVFコンポーネントがPQコンポーネントだけの場合（通常損なわれる）再現率を向上させることである。

以下の図に示すように、PQコンポーネントはさらに細分化できる。データポイントを表す各ベクトルは、固定された数の次元d（上流で使用される埋め込みモデルに応じて、数百または数千のオーダー）を持っている。これだけの32ビットまたは64ビットの浮動小数点数を大量のデータセットで保持することは非常にコストがかかるため、直積量子化はこの問題に2つの段階に分けて取り組む。最初の段階は粗い量子化段階で、ベクトルはm個のサブベクトルに分割され、各サブベクトルは次元d/mを持つ。そして、各サブベクトルには、元のベクトルをその部分空間の点の重心にマッピングする量子化された値（「再生値」と呼ばれる）が割り当てられる。

第二段階はk-meansクラスタリングに似ており、元のベクトルと量子化されたベクトルの重心との間の距離を最小化することで「コードブック」の値が学習される。大きな高次元のベクトルを小さな低次元のサブベクトルにマッピングすることで、格納されるのは量子化された値のコードブックのみとなり、メモリ使用を大幅に削減する。


直積量子化: Pineconeブログを参考にした図

IVFはその後、PQベクトル空間に適用される。この空間内の各点には、他の任意の点よりもソース点（シード）に近い空間内のすべての点で構成される領域、いわゆるボロノイセルという対応する領域がある。これらのシード点は、各重心と空間内のベクトルのリストとの関連を示す転置インデックスを作成するために使用される。

クエリベクトルがどこに位置するかによっては、複数のボロノイセルの境界に近い場合があり、どのセルから最近傍を返すかが曖昧になり、エッジ問題が生じる可能性がある。その結果、IVF-PQインデックスでは、n_probesという追加のパラメータを設定する必要がある。これは、検索アルゴリズムに、n_probesパラメーターで指定されたセルの数だけ外向きに拡張するよう指示します。

IVF-PQインデックスを効果的に構築するためには、PQステップのサブベクトル数とIVFステップのパーティション数の2つを選択する必要がある。サブベクトルの数が多いほど、各サブスペースは小さくなり、圧縮による情報の損失を減らすことができる。しかし、サブベクトル数が多いほど、各PQステップ内でのI/Oと計算が多くなるため、計算コストを低く抑えるためには、この数を最小限に抑える必要がある。

同様に、IVFステップのパーティション数は、再現率と探索速度のトレードオフのバランスをとるように選択しなければならない。パーティション数がデータセット内のベクトル数と等しくなる究極のケースは総当り検索であり、これは最も正確であるが（再現率は1）、質的にIVF-Flatインデックスとなる。

実際、LanceDBのIVF-PQインデックスのドキュメント[7]には、インデックスを作成する際の、まさにこのようなトレードオフが記述されている。したがって、実際のシナリオでどのように適用するかを理解するためには、これらの概念をさらに深く探る価値がある。

HNSW

Hierarchical Navigable Small-World（HNSW）グラフは、ベクトルインデックスを構築するための最も人気のあるアルゴリズムである。この投稿を書いている時点で、ほぼすべてのデータベースベンダーがこれを主要なオプションとして使用している。また、これは最も直感的なアルゴリズムの1つでもあり、これを紹介した元の論文を一読することを強く推奨する。

概要として、HNSWはスモールワールドグラフ現象を基に構築されている。これは、グラフ内のほとんどのノードが互いに隣接していなくても、任意のノードの隣接ノードは、グラフのサイズに関係なく、互いに隣接している可能性が高いという事実に基づいている。基本的に、グラフ内の任意のノードは、比較的少数のステップで他のすべてのノードから到達できる。以下の例では、実線で塗りつぶされた青と赤のノードは、グラフ内で遠く離れていると感じられるかもしれないが、互いにわずか3回のホップで到達できる。

データが存在するベクトル空間は、ナビゲーション可能なスモールワールド(NSW) グラフとしても考えることができる。このグラフでは、ノードはデータポイントを表し、エッジは類似性、つまり、ベクトル空間での2つのノードのどれだけ近いかを示す数値を表す。NSWは、グローバルな接続性、つまり任意のエントリーポイントからグラフ内の任意のノードにアクセスできるように、無向グラフを構築することで動作する。長いエッジ（多くのトラバーサルが必要な遠く離れたノードを接続する）は最初に形成され、短いエッジ（近くのノードを接続する）は後に形成されます。長いエッジは検索効率を向上させ、短いエッジは検索精度を向上させる[3:1]。与えられたクエリベクトルに最も近いノードは、このグラフをたどることで見つけることができる。

NSWグラフの問題点の1つは、グラフが平坦であることである。特定のノードが密集した「トラフィック・ハブ」を作り、トラバーサル効率を低下させ、複雑度が多対数的になる[8]。HNSWは階層的なグラフ構造によってこの問題に対処し、また各ノードの隣接数の上限を固定することで、探索の複雑さを対数的[8:1]に低減している。基本的な考え方は、最近傍を距離尺度に基づいてグラフの階層に分けることである。グラフの長いエッジは一番上の層（最も疎な層）に保持され、下の各層はその上の層よりも距離の短いエッジを含む。最下層が完全なグラフを形成し、探索は上から下へと行われる。すべての層が互いに「折り畳まれた」場合、HNSWグラフは本質的にNSWグラフとなる。

上のイメージは、最上位レイヤーでの任意の入力点から、クエリベクトルの最近傍が見つかるまで、レイヤーを一度に1つずつ落としながらグラフを高速に探索できることを示している。

IVFに対するHNSWの最大の強みは、複雑で高次元なベクトル空間において高い再現率で近似最近傍を見つけることができることである。実際、HNSWがリリースされた2019年当時のベンチマークデータセットにおいて、再現率を向上させつつも高速であるという点で最先端の成果を出しており、これがその絶大な人気の理由となっている。ただし、検索時にベクトルを圧縮するためのPQのような手法と組み合わせない限り、メモリ効率はそれほど高くない。これらの理由から、QdrantやWeaviateのようなデータベースは、再現率とクエリの待ち時間のトレードオフを調整するための調整ノブも提供しながら、HNSW-PQ[9]のような量子化を伴う複合インデックスを実装している。

Vamana

Vamanaは、最も最近開発されたグラフベースのインデックスアルゴリズムの1つで、2019年のNeurIPSで、Microsoft Research Indiaと共同でSubramanyaらによって初めて発表された。

Vamanaの特筆すべき特徴は以下の通り：

  • Vamanaは、インメモリで動作する（ほとんどのインデックスはこのように設計されている）だけでなく、オンディスクでの動作も想定して、最初から設計されている。Microsoftが提示したその実装は、DiskANNと呼ばれてる。
    • オンディスクのインデックスは、ベクトルデータベースのベンダーにとって大きな実装の課題となっているようで、これはVamanaが他のアルゴリズムと異なる重要な特徴である。
  • メモリに収まりきらないほど大きなデータセットのインデックス作成が可能。重複する部分を持つ小さなインデックスを作成し、これらは簡単に1つの単一インデックスとしてマージが可能で、マージされたインデックスのクエリ性能はデータセット全体に対して作成された単一インデックスと同等になる。
  • また、PQのような既存のベクトル圧縮方法と組み合わせて、DiskANNシステムを動かすVamana-PQインデックスを構築することもできる。データセットの全精度ベクトルを持つグラフインデックスはディスク上に保存され、圧縮されたベクトルはメモリ内にキャッシュされるため、両方の利点を活かすことができる。

Vamanaは、ベクトル空間内のデータポイントを表す各ノードを持つランダムなグラフから始めて、繰り返し有向グラフを構築する。最初の段階では、グラフはよくつながっており、ほぼすべてのノードが互いにつながっている。次に、互いに最も近いノード間の接続性を最大化することを目的とした目的関数を用いてグラフを最適化する。これは、ランダムな短距離のエッジのほとんどを剪定し、同時に（グラフのトラバーサルを高速化するために）互いにかなり離れたノード同士を接続する特定の長距離のエッジを追加することによって行われる。

クエリ時には、エントリーポイントとしてグローバルな重心が選ばれる。検索は、長距離のエッジを経由して適切な方向に迅速に進行し、アルゴリズムがグラフの端までジャンプし、クエリベクトルの最近傍を比較的迅速に絞り込むことができる。下の例では、グローバルな重心であるエントリーポイントからグラフの外縁、そして最近傍までわずか3ホップで移動する。

既に気付いたかもしれないが、Vamanaは検索において「内側から外側へ」というアプローチを提供している。これはHNSWの「外側から内側へ」というアプローチとは対照的で、HNSWでは上層のランダムな（潜在的に遠い）ノードからスタートして内側に進行する。

2023年現在、Vamanaインデックスを実装しているデータベースは多くないが、これはおそらくオンディスクの実装に関連する技術的な課題や、それがレイテンシや検索速度に与える影響のためであろう。現時点で、オンディスクのVamanaインデックスを実装しているベンダーはMilvus[10]だけであり、Weaviate[11]とLanceDB[12]は実験的な実装しか行っていない。しかし、この分野は急速に進化しているため、主要なベクトルDBベンダーの最新の開発状況をウォッチしていくことを強く推奨する！

人気のあるベクトルデータベースで利用可能なインデックス

このシリーズの第1回で示したように、ほとんどのデータベースはHNSWインデックスをデフォルトのオプションとして実装している。

Milvus、Weaviate、Qdrant、LanceDBなどのデータベースでは、直積量子化コンポーネントの圧縮/量子化レベルを制御するためのシンプルな調整ノブを提供しています。これらのインデックスがどのように機能するかの基本を理解することは、ユースケースに適したデータベースとインデックスのパラメータを選択するために重要です。

結論

ベクトル特化型データベースのベンダーは、インデックスやストレージレイヤーの微調整と最適化に何千時間も費やしてきた。これにより、もし大量のデータセットがあり、ベクトル検索クエリに100ミリ秒未満のレイテンシが必要な場合、Weaviate、Qdrant、Milvusのような本格的でスケーラブルなオープンソースデータベースを利用することは、開発者にとってもビジネスにとっても、当然のことのように思える。

  • Flat インデックスは、ベクトルを変更されていない形式で保存し、正確なkNN検索に使用される。最も正確で、同時に最も遅い
  • IVF-Flat インデックスは、検索空間を迅速に絞り込むために転置ファイルインデックスを使用し、総当たり検索よりもはるかに高速ですが、再現率の形でいくらかの精度を犠牲にしている
  • IVF-PQ は、ベクトルを圧縮するためにIVFと直積量子化を組み合わせて使用することで、メモリ使用を削減し、検索を高速化する。純粋な PQ インデックスよりも再現率に優れている
  • HNSW は、圧倒的に最も人気のあるインデックスであり、HNSW-PQ の形で直積量子化と組み合わせて使用されることが多く、IVF-PQ と比較して検索速度とメモリ効率が向上している
  • Vamana は、オンディスクのパフォーマンスに特化して設計・最適化された比較的新しいインデックス。メモリよりも大きなベクトルデータを保存しつつ、HNSW 同様の速度を公約としている
    • しかし、まだ始まったばかり、かつ、オンディスクのパフォーマンスというチャレンジングな課題のため、多くのデータベースはまだ実装する方向には進んでいない

しかし、私の見解では、LanceDBは今後数ヶ月注目すべき最もエキサイティングなデータベースの1つだ。LanceDBは市場で唯一、すべてのベクトルインデックスがディスクベースであるベクトルデータベースだからであり、彼らは一度に複数のフロントで革新を進めているためである。

  • 新しい効率的なカラム型データフォーマット、Lanceを構築、ベクトル検索に最適化しつつ、parquetのモダンな後継を目指している
    • LanceDBが、他のベンダーとは異なり、ディスクベースのインデックス作成に関して自信を持って進めることができるのは、この非常に効率的なストレージレイヤーがあるため
  • 組み込み型（サーバーレス）の専用アーキテクチャをゼロから構築
  • ディスクベースのインデックスにとって大きなパフォーマンス向上となるゼロコピーデータアクセス
  • 追加のインフラストラクチャが不要なデータの自動バージョニング。
  • AWS S3やAzure Blob Storageのようなクラウドストレージプロバイダーとの直接的な統合、これにより既存のデータパイプラインとの統合が非常に簡単

どのデータベースを選択するかに関係なく、これらのツールを使って実験するのに最適な時期であることにみんなが同意することでしょう。この記事には多くの情報が含まれていたと思いますが、以下の参考文献は、ベクトルデータベースの内部構造や、それがどのようにゼロから構築されているかを理解するのに非常に役立ちました。この投稿が興味深いものであったことを願っています。学び続けましょう！🚀

このシリーズの他の記事

脚注

  1. "Not All Vector Databases Are Made Equal", Dmitry Kan on Medium ↩︎

  2. "Trillion-scale similarity", Milvus blog ↩︎

  3. "A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search", arxiv.org ↩︎ ↩︎

  4. "Choosing the right vector index", Frank Liu on Substack ↩︎ ↩︎

  5. "Product quantization for nearest neighbor search", J’egou, Douze & Schmid ↩︎

  6. "Scalar Quantization and Product Quantization", Frank Liu on Zilliz blog ↩︎

  7. "ANN indexes", LanceDB docs ↩︎

  8. "Hierarchical Navigable Small-World graphs paper", Malkov & Yashunin ↩︎ ↩︎

  9. "HNSW + PQ", Weaviate blog ↩︎

  10. "On-disk index", Milvus docs ↩︎

  11. "Vamana vs. HNSW", Weaviate blog ↩︎

  12. "Types of index", LanceDB docs ↩︎

GitHubで編集を提案