🎄🎁 情報検索アドベントカレンダー!🎁🎄 勝手に番外編 ~~わかった気になれるHNSW ~~
こんにちは!株式会社XAION DATAの井上です.同僚のYukihideさんが「情報検索アドベントカレンダー!」というのをやっているので便乗します.
ベクトル検索の文脈でHNSW (Hierarchical Navigable Small World)というアルゴリズムをよく見かけますが,これは自分がなぜか好きなアルゴリズムです。理由は名前を聞くたびにあの曲を口ずさみたくなるからです.(最近はパスポートが期限切れで夢の国に入国できてないな~)
年末ということもあり,頭の中がエレクトリカルパレードですが,アドベントカレンダー勝手に番外編やってきます
(ここまでは人間が書いてます)
HNSWとは?
一言でいうと,近似最近傍探索のアルゴリズムの一種でProbability Skip List + Navigable Small World Graphsを組み合わせたようなアルゴリズムです.
近似最近傍探索(ANN)って?
あるベクトル(点)からの距離が近いベクトル(点)をたぶん見つけてくれるやつです.
ベクトル(点)の数が多いと全部との距離を計算していると大変なので,近いものを高確率で当てれるようにしよう!って感じです

Probability Skip List?
みんな大好きリンクリストを重ねたようなデータ構造です.
例えば [3, 6, 9, 12, 15, 18, 21, 24]というリストがあったときに,以下のように階層化します.

こうすることで早く目的の要素を見つけることができるんです!!
動きとしては
- 一番上のLayer 2からスタートします。
- 右隣の値を確認します。
- 探している値より小さければ、そのまま右に進みます(スキップ!)。
- 探している値より大きい(または行き止まり)なら、一つ下のレベルに降ります。
- これを見つかるまで繰り返します。
例えば12を見つけたいときは以下のように発見します

Layer 2が急行で,Layer 1が準急で,Layer 0が各停みたいなことですね
Navigable Small World Graphs(NSW)
NSWは「点(ベクトル)をノードとして、近いノード同士をリンクしたグラフ」です.
イメージとしては、各ノードが「近い友達リスト」を持っていて、探索はこうなります.
- どこかの開始ノード(entry point)からスタート
- 今いるノードの隣接ノードを見て、クエリ(黄色のノード)に より近い ものがあればそこへ移動
- もう近づけなくなったら(局所最小)いったん止まる

再:HNSWとは?
つまりHNSWとは,NSWをProbability Skip Listのように階層化して,あるベクトル(点)からの距離が近いベクトル(点)を素早く,見つけてくれるアルゴリズムです.
終わりに
自分自身もHNSWについてわかった気でいて,結局深くは理解できてないので正確ではない表現もあると思いますが,あくまでHNSWの触りということでお許しください
Discussion
分かりやすい記事でした!
そして、絵文字のチョイスがいいですね!