OpenSearch:ベクターの概要

ベクターベースの取得

情報化時代において、情報は、テキスト、画像、動画、音声など、複数のモダリティで構成される場合があります。マルチモーダル情報は、色、形状、動作状態、音、空間的関係など、テキストよりも多くの情報を提示できます。

さまざまな分野における情報の様態は大きく変化しました。

マルチモーダル情報は、構造化データと非構造化データの 2 つのカテゴリに分類されます。

非構造化データは、コンピューターが理解するのが困難です。テキストの用語を分析する従来のクエリ メソッドでは、さまざまな分野の検索要件を満たすことができません。この問題を解決するために、OpenSearch Vector Search Edition はベクターベースの取得を提供します。

このトピックでは、ベクターとベクターベースの検索を実行する方法について説明します。

物理的世界で生成された非構造化データは、エンティティ間の関係を識別する構造化された多次元ベクターに変換できます。

次に、ベクター間の距離が計算されます。ほとんどの場合、距離が近いほど、ベクターの類似度は高くなります。ベクターの類似度が最も高い上位 N 個の結果が取得されます。これにより、ベクターベースの取得が実装されます。

ベクター取得アルゴリズム

線形アルゴリズム

線形アルゴリズムは、すべてのベクターデータを線形に処理します。

シナリオ: 取得率 100% が必要な場合は、このアルゴリズムを使用できます。

デメリット: このアルゴリズムは効率が低く、大量のデータを処理する場合、高い CPU 使用率とメモリ使用量が必要になります。

クラスタリングアルゴリズム

量子化クラスタリング

概要

量子化クラスタリングは、K 平均法クラスタリングに基づいて Alibaba Cloud によって開発されたベクター取得アルゴリズムです。このアルゴリズムは、ベクタードキュメントの n 個のセントロイドを求め、各ドキュメントをドキュメントに最も近いセントロイドにクラスタリングします。このようにして、n 個の転置インデックスが構築されます。 n 個のセントロイドと対応する転置インデックスは、量子化クラスタリングインデックス作成の主要な内容です。取得中に、OpenSearch はいくつかのセントロイドとリクエストベクター間の距離を計算し、リクエストベクターに最も近い複数のセントロイドを選択します。次に、OpenSearch は、選択されたセントロイドに対応する転置インデックス内のドキュメントのベクター距離を計算し、リクエストベクターに最も近い上位 K 個のドキュメントを返します。

量子化クラスタリングは、FP16 および INT8 量子化機能をサポートしており、インデックスサイズを削減し、取得パフォーマンスを向上させることができます。ただし、この機能は取得結果を損なう可能性があります。ビジネス要件に基づいて、FP16 および INT8 量子化機能を有効または無効にすることができます。

量子化クラスタリングアルゴリズムは、リアルタイムデータシナリオ、または GPU リソースを使用し、低レイテンシが必要なシナリオに適しています。

パラメータ調整:

詳細については、「量子化クラスタリング構成」をご参照ください。

次の図は、異なる量のデータを処理するためのさまざまなベクターアルゴリズムのパフォーマンスを示しています。

HNSW

概要

Hierarchical Navigable Small World (HNSW) は、近接グラフに基づくベクター取得アルゴリズムです。このアルゴリズムでは、近接グラフを作成し、互いに近いベクター間にエッジを構築する必要があります。ベクターとエッジは、HNSW インデックス作成の主要な内容です。取得中に、OpenSearch はエントリベクターから走査を開始し、リクエストベクターとエントリベクターの各隣接ベクター間の距離を計算し、最も近い隣接ベクターを走査の次のベクターとして選択します。 OpenSearch は、収束が現れるまで、上記のルールに基づいてベクターを走査します。収束とは、OpenSearch が、取得された他のすべての隣接ベクターよりもリクエストベクターに近い、現在のベクターの隣接ベクターを見つけることを指します。

収束を加速するために、HNSW はスキップリストクエリのロジックに基づいて多層近接グラフ構造を構築します。取得は上から下へと進みます。各レイヤーの取得ロジックは、レイヤー 0 を除いて同様です。収束が現れたときに OpenSearch がレイヤー K のベクターを走査する場合、そのベクターはレイヤー K-1 のエントリベクターと見なされ、OpenSearch はレイヤー K-1 の走査を続けます。レイヤー K-1 と比較して、レイヤー K には、距離が長いスパースノードが含まれています。この場合、OpenSearch は、レイヤー K-1 よりも大きなステップサイズと高い反復速度でレイヤー K のベクターを走査します。

パラメータ調整:

詳細については、「HNSW 構成」をご参照ください。

QGraph

概要

Quantized Graph (QGraph) は、OpenSearch によって開発された、HNSW ベースの改良アルゴリズムです。 QGraph は、インデックス構築中にユーザーの生データを自動的に量子化し、グラフインデックスを構築します。 HNSW アルゴリズムと比較して、QGraph アルゴリズムはインデックスサイズを効果的に削減し、メモリオーバーヘッドを節約し、インデックスを元の 1/8 まで削減できます。同時に、整数計算の CPU 命令の最適化により、QGraph のパフォーマンスは HNSW と比較して数倍向上しています。量子化後、ベクターの識別は低下し、QGraph の取得率は HNSW よりも低くなります。実際のシナリオでは、より多くのリコールを使用してこの影響を軽減できます。

QGraph は、int4、int8、または int16 レベルでのデータの量子化をサポートしています。量子化レベルが異なると、ベクターインデックスのメモリ消費量、クエリパフォーマンス、および取得率への影響が異なります。一般に、整数ビット幅が減少するにつれて、ベクターインデックスによって占有されるメモリは小さくなり、パフォーマンスは向上し、取得率は低下します。 int16 量子化は、基盤となる CPU 命令セットに関連する問題のため、パフォーマンスと取得率が量子化されていないデータとほぼ同じです。

パラメータ調整:

QGraph (量子化グラフ) 構成

CAGRA

概要

CAGRA (CUDA ANN GRAph-based) は、近接グラフに基づくベクター取得アルゴリズムです。 CAGRA は NVIDIA GPU の最適化に使用され、高い同時実行性とバッチリクエストのあるシナリオに適しています。

HNSW とは異なり、CAGRA は並列計算用に単層近接グラフを構築します。取得中に、アルゴリズムは反復とともに候補ベクターの順序付きセットを維持します。各反復で、アルゴリズムは候補セットから最も適切な上位 K 個のベクターを取得の開始点として選択し、隣接ベクターで候補セットを更新しようとします。このプロセスは、候補セット内のすべての上位 K 個のベクターが取得の開始点として使用されるまで反復されます。この場合、アルゴリズムは収束したと見なされます。

CAGRA アルゴリズムは、single-CTA と multi-CTA の 2 つのポリシーに基づいて実装されています。 single-CTA は単一のスレッドブロックを使用して単一ベクターの取得を実装します。これは、バッチサイズが大きい場合に効率的です。 multi-CTA は複数のスレッドブロックを使用して単一ベクターの取得を実装します。これにより、GPU の並列計算機能を利用し、バッチサイズが小さい場合に高い取得率を実現できます。ただし、バッチサイズが大きい場合、multi-CTA のスループットは single-CTA のスループットよりも低くなります。実際の呼び出し中にワークロードに基づいて最適なポリシーが自動的に使用されます。

パラメータ調整:

ベクター距離タイプ

ベクターベースの取得のプロセスは、ベクター間の類似度を計算し、類似度に基づいて上位 K 個のベクターを返すことです。ベクター間の類似度は、ベクター間の距離を計算することによって得られます。ほとんどの場合、スコアが小さいほどベクター距離は近くなります。スコアが大きいほど、ベクター距離は遠くなります。

異なるベクター空間では、ベクター間の距離を計算するために異なる距離メトリックが定義されています。 OpenSearch は、ユークリッド距離の二乗と内積という次の距離メトリックをサポートしています。

ユークリッド距離の二乗

ユークリッド距離の二乗とは、平面上の 2 つのベクター間の距離を指します。最も一般的な距離メトリックの 1 つとして、ユークリッド距離の二乗は、2 つのベクター間の座標差の二乗の合計の平方根を計算することによって得ることができます。ユークリッド距離の二乗が小さいほど、ベクターの類似度は高くなります。ユークリッド距離の二乗は、次の式に基づいて計算されます。

内積

内積は、2 つのベクター間のドット積またはスカラー積です。内積が大きいほど、ベクターの類似度は高くなります。内積は、2 つのベクターの対応する要素を乗算し、積を合計することによって計算できます。この距離メトリックは、検索レコメンデーションシナリオでよく使用されます。一般に、内積を計算するかどうかは、アルゴリズムに内積モデルがあるかどうかによって異なります。内積は、次の式に基づいて計算されます。

ベクター取得アルゴリズムの比較