本記事について 2023年10月にSpotifyが新たな近似最近傍探索ライブラリとして「Voyager」を発表した[1]。本記事ではVoyagerについて調べたことや、単語の類似検索をユースケースとした実装サンプル、Annoyとの性能比較の結果を備忘としてメモしておく。 近似最近傍探索とは Voyagerの話に入る前に、近似最近傍探索について説明する。 最近傍探索 (Nearest Neighbor Search)とは、あるベクトルのクエリが与えられたときに、そのクエリと「最も似ているベクトル」をベクトルの集合から見つける技術である。 ナイーブな方法としては、クエリのベクトルと、集合の一つ一つのベクトルとの距離をコサイン類似度などで計算し、最も距離が近いものを抽出する線形探索が考えられる。しかし、このアプローチではO(N)(Nは集合のサイズ)で探索に時間がかかるため、データセットが膨大にな