学習
高速ベクトル探索

ボイジャーとは？

Dec 19, 20241 分で読めます

Voyagerは、高次元ベクトルデータに最適化された近似最近傍（ANN）検索ライブラリです。

シリーズ全体を読む

#はじめに

現代のAIシステムは、膨大なデータセットの中からパターンと関係を見つけるために、最近傍探索(Nearest Neighbor Search: NNS) とベクトル類似性探索に依存している。NNSは与えられたクエリに最も近いデータポイントを特定し、レコメンデーションエンジン、検索プラットフォーム、AI主導の探索ツールのようなアプリケーションに、適切でパーソナライズされた結果を提供することを可能にする。データを高次元ベクトルとして表現することで、ベクトル類似度検索は、余弦類似度やユークリッド距離のような数学的指標を用いて、これらのベクトルの近さを測定する。

NNSは、システムが類似したアイテムを効率的に比較・検索できるようにすることで、AIアプリケーションにおいて重要な役割を果たしている。例えば、推薦システムは、ユーザーのリスニング履歴に類似した特徴を持つ曲を特定することができ、画像検索エンジンは、視覚的に関連する結果を検索することができる。このような検索のスピードと精度は、有意義なユーザー体験をリアルタイムで提供するために不可欠である。

大規模かつリアルタイムのベクトル検索に対する需要の高まりに対応するため、Spotifyは検索パフォーマンスを最適化するために設計されたオープンソースのANNライブラリであるVoyagerを開発した。Voyagerは、Hierarchical Navigable Small World (HNSW)アルゴリズムをベースに、スケーラブルで適応的なAIシステムをサポートするために、動的インデックスやマルチスレッドなどの機能を導入している。この記事では、Voyagerのアーキテクチャ、機能、そしてベクトル類似検索の進歩における役割を探る。

Voyagerとは？

Voyagerは高次元のベクトルデータ用に最適化された近似最近傍（ANN）検索ライブラリです。データセットをグラフベースの構造に整理し、高速で効率的な類似検索を可能にします。動的でリアルタイムなシステムをサポートするように設計されたVoyagerは、最新のAI駆動型アプリケーションの進化するニーズに対応することができます。

なぜVoyagerは作られたのか？

Voyagerは、既存のANNライブラリ、特にSpotifyが以前依存していたAnnoyで遭遇した特定の課題に対処するために開発された。Annoyはツリーベースのインデックス作成アプローチを採用しており、静的なデータセットではうまく機能するが、データが変化する環境では頻繁に苦労する。Annoyは、新しいデータが追加されるたびにインデックスの完全な再構築を必要とし、非効率と運用上の課題につながる。

さらに、Spotifyのデータセットが数十億のベクトルに成長するにつれ、Annoyのメモリ使用量とクエリ時間の遅さがボトルネックになった。Spotifyは、HNSWアルゴリズムを実装したHNSWlibなど、他のライブラリも検討しました。HNSWlibは性能と精度は良かったものの、フォールトトレランスや多言語サポートなど、量産に耐えうる機能が欠けていた。

Voyagerはこれらの課題を克服するために作られた。Voyagerの機能を見てみよう。

ボイジャーの機能

Voyagerは、グラフベースのナビゲーション、ダイナミックインデキシング、マルチスレッド操作の組み合わせにより、効率性と柔軟性を実現している。これらの機能により、高速かつ正確な結果を提供しながら、大規模で高次元のデータセットを扱うことができます。

コアメカニズムグラフベースのナビゲーション

Voyagerの中核には、ベクトルをグラフ構造に整理するHNSWアルゴリズムがある。グラフの各ノードはデータポイントを表し、エッジはベクトル空間での近接性に基づいてノード間を結ぶ。グラフは階層構造になっており、幅広い探索と精密な絞り込みのバランスがとれた層になっている。

上位層:** 疎な接続はデータセットの迅速な探索を可能にし、候補を効率的に絞り込む。
下層：*** 密接な接続は、より小さなデータ点のサブセット内での精密な探索を容易にする。

次の図は、HNSWグラフの階層構造を示している：

図- HNSWの論文から、階層グラフの概念を視覚化した図](https://assets.zilliz.com/Figure_A_diagram_from_the_HNSW_paper_that_visualizes_the_layered_graph_concept_631628e4b1.png)

図レイヤードグラフの概念を視覚化したHNSW論文の図。| 出典](https://arxiv.org/abs/1603.09320)

この図では、より少ないノードが接続されているレイヤー2から検索が開始される。これにより、アルゴリズムは関連性のある広い領域を素早く特定することができる。次に、レイヤー1で候補を絞り込むために、より多くの接続が評価される。最後に、最も密な接続を含むレイヤー0で、最近傍が高精度で識別される。

ユーザーの好きな曲に似た曲を推薦する音楽ストリーミングサービスを考えてみよう。レイヤー2では、アルゴリズムは疎な接続をナビゲートし、ポップ、ロック、クラシックのような大まかなカテゴリーを識別し、ポップのような関連するジャンルに検索を誘導する。レイヤー1では、ポップカテゴリー内でより多くのコネクションが評価され、シンセポップ、インディポップ、エレクトロポップのようなサブジャンルに絞り込まれる。このステップでは、ユーザーのクエリに近いスタイル的特徴を持つトラックに検索を集中させる。最後に、レイヤー0で、アルゴリズムは精度の高いマッチングを行い、シンセポップのサブジャンル内で、クエリのトラックとテンポ、ボーカルスタイル、楽器編成などの属性を共有する特定の曲を特定します。この多層的なアプローチにより、パーソナライズされたレコメンデーションを生成する速度と精度の両方が保証される。

この階層的アプローチにより、検索の複雑さが対数になるため、Voyagerは大規模なデータセットを効率的にナビゲートすることができます。

ダイナミック・インデックス作成

静的ライブラリとは異なり、Voyager はベクターの追加、更新、削除をリアルタイムでサポートします。この機能により、インデックスの完全な再構築が不要になり、データが進化してもシステムの応答性が維持されます。例えば、音楽推薦システムでは、ユーザ体験を中断することなく、新しい曲を追加したり、古い曲を削除したりすることができます。

マルチスレッド操作

Voyagerはマルチスレッドを活用してインデックス作成とクエリのパフォーマンスを向上させます。複数のCPUコアにタスクを分散させることで処理時間を短縮し、スループットを向上させます。この機能は、リアルタイム環境で大量のクエリを処理するために不可欠です。

Voyager の主な機能

Voyagerは、最新のAIアプリケーションにおけるベクトル検索のための信頼性の高いツールとなるいくつかの機能を備えています。

スケーラビリティ

Voyagerは、パフォーマンスを損なうことなく数十億のベクトルを処理できるように設計されています。これは、E4M3 8 ビット浮動小数点表現のようなメモリ効率の高いテクニックを使用することで、精度を維持しながらリソースの消費を抑えることで実現しています。このスケーラビリティにより、Voyagerはエンタープライズ規模の導入に適しています。

リアルタイム・アップデート

動的なインデックス作成はVoyagerの主要な機能の一つであり、システムがダウンタイムなしに新しいデータを統合したり、既存のエントリを更新したりすることを可能にします。この機能は、レコメンデーション・エンジンのような、データが常に進化するアプリケーションにとって極めて重要です。

高精度

近似的な手法を使用しているにもかかわらず、Voyagerは階層的なグラフ精密化によって高い精度を実現します。また、開発者はパラメータを調整することで、速度と想起のバランスをとり、特定のアプリケーションのニーズに合わせてVoyagerを調整することができます。

生産に適した設計

Voyagerは、インデックスファイルの破損検出など、フォールトトレラント機能を組み込んでいます。クラウド互換の設計はストリームベースのI/Oをサポートし、分散システムでの展開を簡素化します。

CPUベースのオペレーションに最適化

VoyagerはCPU上で効率的に動作するように設計されており、シンプルさと幅広い互換性を優先するためにGPUアクセラレーションは見送っています。このアプローチは、デプロイを簡素化し、特殊なハードウェアへの依存を減らし、Voyagerが多様な環境に容易に統合できることを保証します。

他のライブラリとの比較

Voyagerは、成長を続けるANNライブラリのエコシステムの中に存在する。それぞれに強みと限界があり、特定のユースケースに適している。

VoyagerとAnnoyの比較

Annoyは、SpotifyがANN検索に使用した初期のライブラリの一つである。これはツリーベースのインデックスに依存しており、静的なデータセットには効果的だが、更新の際にはインデックスの再構築が必要となる。Voyagerはこの制限を動的インデックスで解決しており、リアルタイムで動的なアプリケーションにより適している。さらに、Voyagerは、特にデータセットが大きくなるにつれて、スピードと精度の点でAnnoyを上回る。

Voyagerとhnswlibの比較

HnswlibはHNSWアルゴリズムの有名な実装です。優れたパフォーマンスと精度を提供する一方で、多言語サポートやフォールトトレランスのようなプロダクショングレードの機能が欠けている。Voyagerはhnswlibにこれらの機能拡張を加えることで、より堅牢で多用途なツールに仕上げています。

VoyagerとScaNNの比較

ScaNN は Scalable Nearest Neighbors の略で、内積探索に優れていますが、動的なデータセットをサポートしていません。この制限により、頻繁な更新を必要とするリアルタイムシステムにはあまり適していない。Voyagerは柔軟性があり、進化するデータをサポートしているため、動的な環境にはより適している。

VoyagerとFaissの比較

Faiss は、GPUによるバッチ処理に最適化されており、トレーニングや大規模データセットの前処理のようなオフラインタスクに最適です。対照的に、Voyagerはリアルタイム・アプリケーション向けに設計されており、CPUベースのオペレーションにより、動的なインデックス作成と低レイテンシの応答が可能です。

これらの比較から、Voyagerはベクトル検索ライブラリとして優れていることがわかるが、検索以外のニーズにも対応するベクトルデータベースとの比較を見てみよう。

ベクター検索ライブラリとベクターデータベースの比較

ベクター検索ライブラリとベクターデータベースは、ベクターデータの管理と検索において異なる目的を果たします。Voyagerのようなライブラリが速度と効率的なインメモリ操作に重点を置いているのに対し、ベクターデータベースは永続的なストレージ、分散スケーラビリティ、高度なクエリといった追加機能を提供します。この2つのどちらを選ぶかは、アプリケーションの特定のニーズに依存します。

ベクトル検索ライブラリ

ベクトル検索ライブラリは、迅速なクエリと動的な更新のために設計されており、データが頻繁に変更されるリアルタイム・アプリケーションに最適です。これらのライブラリは完全にメモリ内で動作するため、低レイテンシでの応答が可能ですが、長期的なデータ保存や複雑なワークロードの処理には限界があります。例えば、Voyagerのようなライブラリは、データセットがリアルタイムで更新されるレコメンデーション・エンジンやパーソナライズされた検索プラットフォームに最適です。

しかし、これらのライブラリは永続的なストレージや分散システムのビルトインサポートを提供しないため、ユーザーはインフラとデータのライフサイクルを手動で管理しなければならない。このためライブラリは、データの永続性や規模よりもスピードを優先するシナリオに適している。

ベクター・データベース

ベクターデータベースは、永続ストレージ、分散アーキテクチャ、および大規模データセットのクエリ最適化を組み込むことで、ライブラリの機能を拡張します。ベクターデータベースは、ベクターデータを長期にわたって管理し、システムの再起動を経てもデータの永続性とアクセシビリティを維持できるように構築されています。類似検索に加えて、ベクトルデータベースはベクトルベースの検索と構造化メタデータのフィルタリングを組み合わせたハイブリッドクエリをサポートすることが多い。

Zillizによって作成されたオープンソースのベクトルデータベースであるMilvusは、専用に構築されたベクトルデータベースの主要な例である。Milvusは大規模なベクトルデータセットを管理するために設計されており、データ量の増大とクエリ要求の増大に対応するために水平スケーリングをサポートしている。Milvusはハイブリッド検索を可能にし、類似検索とタイムスタンプやカテゴリなどの追加属性によるフィルタリングを組み合わせることができる。また、ハイブリッド全文検索とベクトル検索もサポートしている。この機能により、電子商取引のレコメンデーション、画像検索、ビデオ分析アプリケーションに適している。

また、ZillizはZilliz Cloudを提供しています。これはMilvusが提供するマネージドベクトルデータベースサービスで、導入とメンテナンスを簡素化します。Zilliz CloudはMilvusの全機能を提供する一方、インフラ管理に伴う運用上のオーバーヘッドを排除する。そのため、バックエンドの複雑な処理を行う必要なく、ベクトル検索機能を拡張しようとする組織にとって良い選択肢となる。

それぞれを使用する場合

ベクター検索ライブラリとベクターデータベースのどちらを選択するかは、アプリケーションの特定の要件に依存します：

Voyager のようなライブラリは、迅速なクエリとリアルタイムの更新を必要とするアプリケーションに使用します。Voyager のようなライブラリは、迅速なクエリとリアルタイムの更新を必要とするアプリケーションに使用します。
永続的ストレージ、分散スケーラビリティ、高度なクエリ機能が必要な場合は、Milvusのようなデータベースを選択する。ベクターデータベースは、大規模データセット、ハイブリッド検索ニーズ、高可用性とスケーラビリティを必要とするアプリケーションを含むエンタープライズユースケースに適しています。

結論

Voyager は、リアルタイムの高次元データアプリケーションのニーズを満たすように設計された、近似最近傍（ANN）検索のための効果的なソリューションを提供する。動的なインデックス作成、グラフベースのナビゲーション、スケーラビリティにより、進化するデータセットを迅速かつ正確に管理するための信頼性の高いツールとなっている。

Voyagerのようなライブラリは、高速なクエリを優先する軽量なリアルタイムアプリケーションに適している。しかし、Milvusのようなベクトルデータベースは、永続的なストレージ、スケーラビリティ、高度な検索機能が必要な場合に、包括的な代替手段を提供します。これらのツールを組み合わせることで、ベクトル検索の幅広い要件に対応し、最新のAIアプリケーションの高まる要求をサポートします。

その他のリソース

spotify/voyager: 🛰️ 使いやすさ、シンプルさ、展開のしやすさを重視した、PythonとJavaのための近似最近傍探索ライブラリ
Voyagerの紹介：Spotifyの新しい最近傍検索ライブラリ - Spotify Engineering : Spotify Engineering](https://engineering.atspotify.com/2023/10/introducing-voyager-spotifys-new-nearest-neighbor-search-library/)
voyager/README.md at main - spotify/voyager
階層的ナビゲーシブルスモールワールド(HNSW)の理解 - Zilliz blog](https://zilliz.com/learn/hierarchical-navigable-small-worlds-HNSW)
Faiss (Facebook AI Similarity Search)とは - Zilliz blog](https://zilliz.com/learn/faiss)
ANNベンチマークを理解する](https://zilliz.com/glossary/ann-benchmarks)
ベクターデータベースのベンチマーク：テクニックと洞察 - Zilliz blog](https://zilliz.com/learn/benchmark-vector-database-performance-techniques-and-insights)
VectorDBBench: オープンソースのベクトルデータベースベンチマークツール - Zilliz blog](https://zilliz.com/learn/open-source-vector-database-benchmarking-your-way)