ベクトル検索 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 の設計を出発点として、条件を変えながら検証を続けています。
関連論文にはさまざまな見方や結果があります。それぞれの前提や評価条件を参照しながら、量子化方法やベクトルの幾何学的な特徴を含めて研究を進めています。一部の成果は特許出願中であるため、公開できる範囲から順次紹介します。