Spotify Voyager：Annoy から進化した、高速・高精度な近傍探索ライブラリ

概要

近年、Eコマースサイトの商品推薦や、TikTokやSpotifyといったコンテンツ配信サービスにおけるレコメンド機能の重要性は増すばかりです。ユーザーの好みや行動履歴に基づいた関連性の高い提案は、ユーザー満足度を向上させ、結果として売上アップにも繋がります。
実際にTikTokの推薦アルゴリズムが世論に大きな影響を与えたり、強い中毒性を持っていることは皆さんよく実感されていると思います。
レコメンドシステムを構築する手法は多岐にわたりますが、中でも 類似アイテム検索 は、ユーザーが現在閲覧している商品や、過去に購入・視聴したアイテムと似たものを提示する、非常に効果的なアプローチです。このコンテンツベースの方法は、ユーザーの行動データを利用せずに推薦することができるためサービス初期から導入することができます。

既存の手法との簡単な比較

類似アイテムを検索するためには、まずアイテムの特徴を数値化し、ベクトルとして表現する必要があります。例えば、商品の説明文を単語の出現頻度でベクトル化したり、画像から Convolutional Neural Network (CNN) を用いて特徴量を抽出したりする方法が考えられます。そして、これらのベクトル間の距離を計算することで、アイテム間の類似度を測ることができます。

しかし、アイテム数が膨大になるにつれて、全てのアイテム間の距離を計算するのは現実的な時間では終わりません。そこで注目されるのが、近似最近傍探索 (Approximate Nearest Neighbor Search, ANNS) という技術です。ANNS は、厳密な最近傍を見つける代わりに、それに近いアイテムを高速に探し出すための手法です。

本記事では、数ある ANNS アルゴリズムの中でも、Spotify が開発したオープンソースライブラリである Spotify Voyager に焦点を当て、その技術的な側面から実際の活用事例までを深掘りしていきます。実は、以前に私が Annoy (Approximate Nearest Neighbors Oh Yeah) を用いた類似商品検索システムの構築についてブログ記事を書きました。今回の記事では、その前世代ライブラリである Annoy の課題を乗り越え、更なる進化を遂げた Voyager の魅力に迫ります。

Spotify Voyager とは？特徴と背景

Spotify Voyager は、大規模なデータセットにおける高速かつ高精度な近似最近傍探索を実現するために開発された C++ で記述されたライブラリであり、Python と Java からの呼び出しも提供されています。Spotify の音楽レコメンデーションシステムをはじめ、様々なプロダクトの裏側を支える重要な技術です。

特徴

• 驚異的な検索速度: Voyager の核となる HNSW (Hierarchical Navigable Small Worlds) アルゴリズムは、前世代のライブラリである Annoy と比較して、最大 10 倍もの高速な検索を実現します。
• 高精度な検索結果: 高速であるだけでなく、Voyager は Annoy と同等のリコール率を維持しながら、最大 50% 高い精度を提供します。これは、より関連性の高いアイテムをユーザーに提示できることを意味します。
• 優れたメモリ効率: Voyager は、Annoy と比較して最大 4 分の 1 のメモリ消費で動作します。さらに、HNSW の一般的な実装である hnswlib と比較しても 16 分の 1 という驚異的なメモリ効率を誇ります。これは、大規模なデータセットを扱う上で非常に重要な利点となります。
• マルチスレッド対応: インデックスの作成と検索の両方においてマルチスレッドをサポートしており、CPU リソースを最大限に活用することで、処理時間を大幅に短縮できます。
• 幅広い言語サポート: Python と Java の両方のバインディングを提供しており、開発者は自身の得意な言語で Voyager の機能を利用できます。また、両言語間で機能の同等性とインデックスの互換性が保証されています。
• プロダクション環境での実績: Spotify のプロダクション環境で大規模に利用されており、その安定性と信頼性は実証済みです。日々、数億件ものクエリを処理し、ユーザー体験を支えています。
• インメモリデータベース: Voyager はインメモリで動作するため、専用のデータベースサーバーを必要としません。これにより、セットアップが容易になり、運用コストを削減できます。

やはり実際の大規模なプロダクトで動いている実績があるのはスケーリングや信頼性に大きな安心感がありそうです。

背景

Voyager が開発された背景には、Spotify が長年利用してきた近似最近傍探索ライブラリである Annoy の存在があります。Annoy は、そのシンプルさと使いやすさから広く利用されてきましたが、データ量の爆発的な増加に伴い、いくつかの課題が顕在化してきました。具体的には、大規模なデータセットにおける検索速度の低下や、メモリ消費量の増大、そして精度の限界といった点が挙げられます。これらの課題を解決するために、Spotify はより高性能な次世代の ANNS ライブラリとして Voyager を開発したのです。

Voyager の技術的側面：高速・高精度を支える仕組み

なぜこんなにもVoyagerは早いのでしょうか？

Voyager の高速かつ高精度な検索性能は、いくつかの ключевых 技術要素によって支えられています。

最も重要な要素の一つが、Voyager の心臓部とも言える HNSW (Hierarchical Navigable Small Worlds) アルゴリズム です。HNSW は、データポイントを階層的なグラフ構造で表現することで、効率的な最近傍探索を可能にするアルゴリズムです。最上位層のグラフは疎であり、大まかな検索を高速に行い、下位層に進むにつれて密なグラフとなり、より詳細な検索を行います。この階層的な構造により、探索範囲を効率的に絞り込むことができ、高速な検索を実現しています。

さらに、Voyager は SIMD (Single Instruction, Multiple Data) 命令 を積極的に活用しています。SIMD 命令は、一つの命令で複数のデータに対して同時に演算を実行できる CPU の機能であり、特に距離計算のような並列化可能な処理において、大幅な高速化に貢献します。Voyager は、x86_64 環境では AVX2、ARM 環境では NEON といった最新の SIMD 命令セットをサポートし、ハードウェアのポテンシャルを最大限に引き出しています。

メモリ効率の面では、Voyager はインデックス構造の最適化や、メモリマップドファイルの利用など、様々な工夫を凝らしています。メモリマップドファイル を利用することで、インデックス全体をメモリにロードする必要がなくなり、メモリ使用量を大幅に削減できます。必要な部分だけをオンデマンドでメモリに読み込むため、大規模なインデックスでも効率的に扱うことができます。

Voyager は、コサイン類似度、ユークリッド距離、内積など、様々な 距離関数 をサポートしており、アプリケーションの要件に合わせて最適なものを選択できます。
それぞのの類似度には特徴があるようなので、活用シーンによって使い分けていきたいですね。

Voyager vs. Annoy：進化のポイントの比較

特徴	Annoy	Voyager
アルゴリズム	ランダム射影木 (Random Projection Trees)	階層的航行可能なスモールワールド (HNSW)
検索速度	比較的遅い	大幅に高速 (最大 10 倍)
精度	同程度	同等以上 (最大 50% 向上)
メモリ効率	比較的高い	大幅に効率的 (最大 4 分の 1)
スケーラビリティ	大規模データで性能低下	大規模データに強い
並列処理	限定的	インデックス作成・検索で強力な並列処理をサポート
距離関数	コサイン類似度、ユークリッド距離 etc...	多様な距離関数をサポート

Spotify における Voyager の活用事例：大規模サービスを支える技術

Spotify は、その大規模な音楽ストリーミングサービスにおいて、Voyager を中心とした様々な技術を活用しています。

• 音楽レコメンデーション: ユーザーの過去のリスニング履歴や作成したプレイリスト、お気に入りのアーティストなどの情報に基づいて、Voyager はユーザーが興味を持ちそうな楽曲を高速かつ高精度に推薦します。パーソナライズされたプレイリストの自動生成にも Voyager が活用されており、ユーザーに新たな音楽との出会いを提供していいるそうです。
• 楽曲の重複排除: Spotify には毎日膨大な数の楽曲がアップロードされますが、その中には重複している楽曲も存在します。Voyager は、楽曲のオーディオフィンガープリント (楽曲の音響的な特徴を数値化したもの) をベクトル化し、それを高速に比較することで、ほぼ同一の楽曲を効率的に特定し、重複を排除します。これは、著作権管理やストレージの効率化に大きく貢献しています。
• ポッドキャストのレコメンデーション: 音楽だけでなく、ポッドキャストのレコメンデーションにも Voyager が活用されています。ユーザーのポッドキャスト視聴履歴や興味関心に基づいて、おすすめのポッドキャストやエピソードを推薦することで、ユーザーエンゲージメントの向上に貢献しています。

これらの事例からもわかるように、Voyager は Spotify の様々な機能において中核的な役割を果たしており、日々の膨大なリクエストを高速かつ安定的に処理することで、世界中の音楽ファンに快適な音楽体験を提供しているそうです。

Voyager を使ってみよう：簡単な実装例

以前のブログ記事では Annoy を用いた実装例を紹介しましたが、ここでは Voyager を使った simpleな実装例を Python で示します。

import numpy as np
from voyager import Index, Space

# VoyagerのIndexオブジェクトを作成します。
# Space.Euclideanは距離空間としてユークリッド距離を使用することを指定します。
# num_dimensions=5は、格納するベクトルの次元数が5であることを示します。
index = Index(Space.Euclidean, num_dimensions=5)

# インデックスにアイテム（ベクトル）を追加します。
# add_itemメソッドは、追加されたアイテムの内部IDを返します。
id_a = index.add_item(np.array([1, 2, 3, 4, 5], dtype=np.float32)) # NumPy配列を渡す
id_b = index.add_item(np.array([6, 7, 8, 9, 10], dtype=np.float32)) # NumPy配列を渡す

print(id_a)  # => 0  # 最初に追加されたアイテムのIDは0になります
print(id_b)  # => 1  # 次に追加されたアイテムのIDは1になります

# 指定されたベクトルに最も近いk個の要素を検索します。
# queryメソッドは、最も近い要素のIDのリストと、それらの距離のリストを返します。
# 第一引数には検索クエリとなるベクトルを指定します。
# k=2は、最も近い2つの要素を検索することを指定します。
neighbors, distances = index.query(np.array([1, 2, 3, 4, 5], dtype=np.float32), k=2) # NumPy配列を渡す
print(neighbors)  # => [0, 1] # 最も近い要素はID 0 と 1 のアイテムです
print(distances)  # => [0.0, 125.0] # ID 0 のアイテムとの距離は 0.0、ID 1 のアイテムとの距離は 125.0 です

# 作成したインデックスをディスクに保存します。
# これにより、後で再ロードしたり、Javaなどの他の言語で利用したりできます。
index.save("output_file.voy")

まとめ

Spotify Voyager は、前世代の Annoy の課題を克服し、より高速、高精度、そして低メモリ消費を実現した、次世代の近似最近傍探索ライブラリです。その優れた性能は、Spotify の音楽レコメンデーションシステムをはじめとする様々な機能において、ユーザー体験の向上に大きく貢献しています。

Voyager の登場は、レコメンドシステムや類似アイテム検索の分野に大きなインパクトを与え、より大規模なデータセットに対しても、高速かつ高精度な情報検索を可能にする道を開き、Open sourceでの公開により幅広く人々へ利用のチャンスを作りました。その応用範囲は音楽分野に留まらず、画像検索、などの大規模なデータに対する類似度検索が必要な様々な分野での活用が期待されます。

GitHub でソースコードやドキュメントを閲覧することができます。
興味を持たれた方は、ぜひ以下のリンクから詳細をご確認ください。

Voyager GitHub リポジトリ: https://github.com/spotify/voyager