コンテンツにスキップ

ベクトル検索 ANN

大規模なベクトルデータに対する近似最近傍探索(ANN)を、検索精度、計算量、メモリ効率の面から研究するプロジェクトです。

LSH Cascade PoCで行ったベクトル検索の実装実験を引き継ぎ、IVF系の探索、Voronoi分割、量子化、ベクトルの幾何学的な特徴へと研究対象を広げています。

プロジェクトの目的

ベクトル検索では、データ規模が大きくなるほど、全件との類似度計算が難しくなります。一方で、候補を強く絞りすぎると、本来取得すべきベクトルを失う可能性があります。

本プロジェクトでは、次のテーマを中心に検証を進めています。

  • Voronoi分割を利用した探索候補の絞り込み
  • 一つのベクトルを複数のセルへ割り当てる方法
  • SQ8をはじめとする量子化方法
  • ベクトルが持つ幾何学的な特徴の分析
  • CPUとメモリの制約を考慮した大規模検索

LSH Cascade PoCからの発展

LSH Cascade PoCでは、ITQ-LSHと段階的な候補の絞り込みを組み合わせ、ベクトル検索を軽量に実現する方法を検証しました。

その後の実験では、LSHだけに限定せず、IVF系の探索を含む複数の方法を比較しています。Ploneの実データを用いた約800件規模の検証から始まり、現在は最大1,000万件、5種類以上のEmbeddingモデルを使った検証まで規模を広げています。

現在の状況

Voronoi分割と、一つのベクトルを二つのセルへ割り当てる A=2 の設計を出発点として、条件を変えながら検証を続けています。

関連論文にはさまざまな見方や結果があります。それぞれの前提や評価条件を参照しながら、量子化方法やベクトルの幾何学的な特徴を含めて研究を進めています。一部の成果は特許出願中であるため、公開できる範囲から順次紹介します。

ベクトルの特徴を、索引の比較に生かす

方向集中度(cos_mean)や次元活用率(PR/D)で分布を確認し、量子化誤差や再スコアリングに必要な候補数との関係を検証しています。索引を構築する前に、どの情報から比較条件や候補数を見積もれるかを調べています。

ランダム回転を用いるRaBitQの予備実験では、スペクトルから誤差の大きさを予測する当初の仮説を支持しない結果が得られました。前処理が元の順位を保つかを確認したうえで、量子化誤差と近傍のスコア間隔を分けて調べています。候補数の予測は、較正用クエリの厳密スコアを使った小規模な条件での検証段階です。

また、pgvectorの回転を使わない二値量子化では、中心化によって改善するモデルと悪化するモデルの両方を確認しました。方向集中度だけで中心化を勧めず、同じ標本で中心化の有無を比較し、量子化による候補選択と近似探索の影響を分けて評価する方針です。

Vector Search Checkupでは、手元のベクトルの分布や幾何学的な特徴を確認できます。診断値だけで最適な索引や検索品質が決まるわけではなく、実際のクエリを使った検索品質、速度、メモリ使用量の評価へつなげます。

8モデルで中心化の効果を比較した結果を、pgvectorの二値量子化、中心化の効果はモデルで変わるで紹介しています。

実装への応用と今後の報告

PostgreSQLでは、ベクトルの特徴を判定するSQL文や、本格的な拡張にする前の機能づくりに取り組んでいます。中心化した二値量子化の式索引を作成・利用できることも実験で確認しました。中心化の効果の比較、計算結果の確認や処理負荷を含め、具体的な使い方を改めて報告する予定です。

LanceDBについても、索引や再スコアリングの検証、実装上の課題と改善提案を、個別の事例として紹介していきます。診断と索引選びを結びつけるアドバイザのツール化は、こうした検証や利用者からの反応を踏まえて検討します。

関連リンク