プロジェクトに適したベクトルインデックスの選択
プロジェクトに適したベクトルインデックスの選択
簡単なまとめ
ベクターデータベース101シリーズ](https://zilliz.com/blog?tag=39&page=1)では、ベクターデータベースは、高次元ベクトル(通常96次元以上、時には10k次元以上)の大規模なデータセットに対して近似最近傍探索を行うことを目的としたデータベースであることを学んだ。これらのベクトルは、非構造化データ、すなわち、リレーショナル・データベース、ワイド・カラム・ストア、ドキュメント・データベースのような従来のデータベースに収まらないデータのセマンティクスを表現するためのものである。
効率的な類似検索を行うには、ベクトルインデックスとして知られるデータ構造が必要である。このようなインデックスにより、各ベクトルに対して総当り検索を行うのではなく、データベース全体を効率的に走査することができる。インメモリ・ベクトル検索のアルゴリズムとインデックス作成ストラテジーは数多くあります。それぞれの概要を簡単に説明します：
ブルートフォースサーチ (FLAT)
ブルートフォースサーチ（"フラット "インデクシングとも呼ばれる）は、クエリベクトルをデータベース内の他のすべてのベクトルと比較するアプローチです。素朴で非効率的に見えるかもしれませんが、フラット・インデックス作成は、特にGPUやFPGAのようなアクセラレータで並列化した場合、小規模なデータセットでは驚くほど良い結果を得ることができます。
フラットに可視化](https://assets.zilliz.com/Flat_visualized_3173e0ea74.png)
反転ファイルインデックス (IVF)
IVFはパーティションベースのインデックス作成戦略であり、すべてのデータベースベクトルを最も近いセントロイドを持つパーティションに割り当てる。クラスタのセントロイドは教師なしクラスタリング（典型的にはk-means）を使って決定される。セントロイドと割り当てが完了したら、転置インデックスを作成し、各セントロイドとそのクラスタ内のベクトルリストを関連付けます。IVFは一般的に、小規模から中規模のデータセットに適した手法です。
二次元ボロノイ図 画像：Balu Ertl](https://assets.zilliz.com/A_two_dimensional_Voronoi_diagram_Image_by_Balu_Ertl_58ec218a53.png)
スカラー量子化 (SQ)
スカラー量子化 は、浮動小数点ベクトル (典型的には float32 または float64) を、各次元をビンに分割することで整数ベクトルに変換します。この処理には
各次元の最大値と最小値を決定する。
開始値とステップ・サイズの計算。
開始値を減算し、ステップ・サイズで除算して量子化を実行する。
量子化されたデータセットには通常8ビットの符号なし整数が使われるが、それ以下の値（5ビット、4ビット、さらには2ビット）もよく使われる。
積量子化 (PQ)
スカラー量子化は各ベクトルの次元に沿った分布を無視するため，ビンが十分に利用されない可能性がある．積量子化 (PQ) は，圧縮と削減の両方を実行する，より強力な代替手段である：高次元のベクトルは，元のベクトルの固定長のチャンクを1つの量子化された値に割り当てる低次元の量子化されたベクトルにマッピングされる。PQ`は通常、ベクトルを分割し、すべての分割に対してk-meansクラスタリングを適用し、重心インデックスを変換する。
PQ、可視化](https://assets.zilliz.com/PQ_visualized_6ace859fab.png)
階層的航行可能小世界 (HNSW)
HNSWは今日最も一般的に使用されている ベクタリングインデックス戦略である。これは、スキップリストとナビゲー ブル・スモールワールド(NSW)という2つの概念を組み合わせたものです。スキップリストは効果的に階層化されたリンクリストであり、より高速なランダムアクセスを実現する（リンクリストの O(n)に対してスキップリストは O(logn)）。HNSWではNSWの階層グラフを作成する。HNSWでの検索は、最上層から始めて、最も近いものが見つかるまで、各層で最も近い近傍に移動する。挿入は、最近傍を見つけて接続を追加することで機能する。
HNSWの視覚化。Credit: Yu. A. Malkov & D. A. Yashunin](https://assets.zilliz.com/HNSW_visualized_cd132f5126.png)
近似最近傍値 Oh Yeah (Annoy)
Annoyは、バイナリ探索木をコアデータ構造として使用するツリーベースのインデックスである。ベクトル空間を再帰的に分割してバイナリツリーを作成し、各ノードはランダムに選択された2つの子ベクトルから等距離にある超平面によって分割されます。分割プロセスは、葉ノードの要素数があらかじめ定義された数より少なくなるまで続けられる。クエリは、木を反復して、クエリ・ベクトルが超平面のどちらに位置するかを決定する。
迷惑、可視化](https://assets.zilliz.com/Annoy_visualized_ebae75511e.png)
これらの要約が少し難解に感じられても心配しないでほしい。ベクトル探索アルゴリズムはかなり複雑ですが、視覚化とちょっとしたコードで説明しやすくなることがよくあります。
ベクトルインデックスの選択
では、具体的にどのようにして正しいベクトル・インデックスを選べばよいのでしょうか？これはかなり自由な質問ですが、覚えておくべき1つの重要な原則は、適切なインデックスはアプリケーションの要件に依存するということです。例えば、（静的データベースの）クエリ速度に主眼を置いているのか、それとも挿入や削除を多用するアプリケーションなのか。メモリやCPUに制限があるなど、マシンのタイプに制約がありますか？あるいは、挿入するデータの領域が時間の経過とともに変化する可能性はありませんか？これらすべての要因が、使用すべき最適なインデックスタイプを決定します。
ここでは、プロジェクトに適したインデックスタイプを選択するためのガイドラインを紹介します：
100%リコール：100％の精度が必要な場合はFLAT検索を使用する。ベクトル検索用の効率的なデータ構造はすべて近似最近傍探索を行うので、インデックスサイズがある閾値に達すると再現性が低下します。
index_size< 10MB: インデックスのサイズが小さい場合（512次元のfloat32ベクトルが5k個以下）、FLAT` 検索を使用する。インデックスの構築、メンテナンス、クエリに関連するオーバーヘッドは、小さなデータセットでは割に合わない。
10MB < index_size < 2GB：インデックスサイズが小さい場合（512次元の float32 ベクトルが1M以下）、標準的な転置ファイルインデックス（例 IVF）を使用することを推奨する。転置ファイルインデックスは、かなり高い検索結果を維持しながら、検索範囲を1桁ほど小さくすることができる。
2GB < index_size < 20GBである：中程度のインデックスサイズ（512次元の float32 ベクトルが10M以下）になると、他の PQ や HNSW インデックスタイプを検討し始めることになる。どちらも妥当なクエリ速度とスループットを提供してくれるが、PQ は低いリコール率を犠牲にしてメモリ使用量を大幅に減らすことができ、HNSW は高いメモリ使用量（インデックスの合計サイズの約 1.5 倍）を犠牲にして 95% 以上のリコール率を提供することが多い。この範囲のデータセットサイズであれば、複合 IVF インデックス（IVF_SQ、IVF_PQ）もうまく機能するが、計算リソースが限られている場合にのみ使用したい。
20GB < index_size < 200GB：大きなデータセット（512次元の float32 ベクトルが100M以下）には、composite indexes の使用を推奨する：メモリに制約のあるアプリケーションには IVF_PQ を、高い再現性を必要とするアプリケーションには HNSW_SQ を使用する。複合インデックスとは、複数のベクトル検索ストラテジーを1つのインデックスにまとめるインデックス作成技法である。例えば、 HNSW_SQ は HNSW の基本的なクエリ速度とスループットの大部分を保持しながら、インデックスサイズを大幅に縮小している。ここではコンポジットインデックスについて深入りすることはしませんが、FAISSのドキュメントにその概要が記載されていますので、興味のある方はご覧ください。
Annoyに関する最後の注意点として、一般的に言ってパフォーマンスが劣るため、HNSWと同じようなカテゴリーに属するという理由だけで使用することはお勧めしません。Annoyは最もユニークな名前のインデックスなので、ボーナスポイントがある。
ディスクインデックスについて
このブログ記事でまだ明確に説明していないもう一つのオプションは、ディスクベースのインデックスです。一言で言えば、ディスクベースのインデックスは、個々の検索サブスペースを独自のNVMeページにコロケートすることで、NVMeディスクのアーキテクチャを活用します。ゼロ・シーク・レイテンシーと組み合わせることで、グラフベースとツリーベースの両方のベクトル・インデックスを効率的に格納することができます。
これらのインデックス・タイプは、合理的なパフォーマンス・レベルを維持しながら、1台のマシンで数十億のベクターのストレージと検索を可能にするため、ますます人気が高まっています。ディスクベースインデックスの欠点も明らかでしょう。ディスク読み取りはRAM読み取りよりもかなり遅いため、ディスクベースのインデックスではクエリレイテンシが増大することが多く、時には10倍以上になることもあります！最小限のコストで何十億ものベクトルを格納するために、レイテンシとスループットを犠牲にすることを厭わないのであれば、ディスクベースのインデックスが適しています。逆に、アプリケーションに高いパフォーマンスが要求される場合は（多くの場合、計算コストの増加を犠牲にして）、IVF_PQ または HNSW_SQ にこだわることをお勧めします。
まとめ
この投稿では、利用可能なベクターインデキシング戦略をいくつか取り上げました。データサイズと計算量の制限を考慮し、最適な戦略を決定するのに役立つ簡単なフローチャートを提供しました。このフローチャートは一般的なガイドラインであり、厳密なルールではないことに注意してください。最終的には、各インデックスオプションの長所と短所を理解し、また、複合インデックスがアプリケーションに必要な最後の性能を絞り出すのに役立つかどうかを理解する必要があります。これらのインデックスタイプはすべてMilvusで自由に利用することができます。ぜひ試してみてください！
ベクターデータベース101コースをもう一度見てみましょう。
1.非構造化データ入門 2.ベクターデータベースとは 3.ベクトルデータベース、ベクトル検索ライブラリ、ベクトル検索プラグインの比較 4.Milvusの紹介 5.Milvusクイックスタート 6.ベクトル類似検索入門 7.ベクトルインデックスの基本と反転ファイルインデックス 8.スカラー量子化と積量子化 9.階層的航行可能小世界(HNSW) 10.近似最近傍オーイェー(ANNOY) 11.プロジェクトに適したベクトルインデックスの選択 12.DiskANNとVamanaアルゴリズム
Frank LiuDirector of Operations & ML Architect at ZillizFrank Liu is the Director of Operations & ML Architect at Zilliz, where he serves as a maintainer for the Towhee open-source project. Prior to Zilliz, Frank co-founded Orion Innovations, an ML-powered indoor positioning startup based in Shanghai and worked as an ML engineer at Yahoo in San Francisco. In his free time, Frank enjoys playing chess, swimming, and powerlifting. Frank holds MS and BS degrees in Electrical Engineering from Stanford University.
