HNSWの内部構造

11K Views

September 05, 23

スライド概要

HNSW(Hierarchical Navigable Small Worlds)の内部構造、探索ロジック、ファイルへの保存処理について

profile-image

LIFULL HOME'Sを運営する株式会社LIFULLのアカウントです。 LIFULLが主催するエンジニア向けイベント「Ltech」等で公開されたスライド等をこちらで共有しております。

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

hnswの内部 株式会社LIFULL 社内勉強会資料 プラットフォームG 宮崎 泰輔

2.

今日話すこと 1. hnswについて復習 2. SolrのKNNで使用されているベクトル検索のアルゴリズム hnswの内部構造について 3. hnswのグラフ構造をファイルにどう保存するのか 4. ファイルにインデックスを保存する際の話

3.

hnswについて復習 hnswとは Hierarchical Navigable Small Worlds のこと 近傍探索のためのデータ構造とアルゴリズム 近傍探索とは - グラフにおける、ある点から近いものを探し出すタスクのこと - データ数が増えた場合に、コストが指数関数的に増大する

4.

hnswについて復習 1 8 7 2 6 3 9 Q 11 4 5 10

5.

hnswについて復習 人間だったら、この程度なら視覚的に簡単にわかる - 次元数が大きくなって図で表現できなくなったら? - データ数が多くなったら? 全然無理 - コンピュータも同じ - 各ノードごとに距離を計算して近いものだけ取得する必要がある

6.

hnswの復習 基本的なアイデアはスキップリストと同じ - 各駅停車と快速と、特急のようなイメージ - エッジが少ないレイヤーで近づいて、レイヤーを下って詳細に

7.

hnswを実現する具体的な構造(hnswlib) 大まかに2つの構造で構成される - data level0 - level0(全データがあるレイヤー)の一つのノードに以下の情報がある - データ本体 外部のラベル - - 内部用のIDと、外部用のIDがある 近傍ノード達へのリンク - M0 個までリンクを持っている M0の固定長でメモリ確保している - link lists - 各要素の、level1以上のリンク達がある - level数に応じて 可変長 でメモリ確保している 近接ノードへのリンクは、 Mの固定長でメモリ確保している

8.

hnswを実現する具体的な構造(hnswlib) data level0の擬似コード Links = { N: int, data level0<T> = { links: int[maxM0]//internal idの配列 N: int, elements: Element<T>[N] } } Element<T> = { level0 links: Links, Data: T, label: int, } 実行時に、maxM0をもとに、 要素ごとのデータサイズを計算し、 要素数*データサイズでmallocする

9.

hnswを実現する具体的な構造(hnswlib) data level0はココ 全部の要素と、各つながりを 保存している

10.

hnswを実現する具体的な構造(hnswlib) link listsの擬似コード Links = { N: int, link lists = { links: int[maxM]//internal idの配列 N: int, lists per level: *ListPerLevel[N] } } ListPerLevel = { num_levels: int, links: Links[num_levels] } 各要素ごとに、レベルをいくつ 持つかが異なるので、要素ごとに 可変長でメモリを確保している ただし、各レベルにおいては maxMだけ固定長でmallocしている

11.

hnswを実現する具体的な構造(hnswlib) link listsはココ 各要素毎に、レベルがいくつまである かを保存している elem[0] = [ { lists: [1, 2] }, // level1 { lists: [3] }, // level2 ] elem[1] = [ { lists: [0] } // level1 ]

12.

hnswのグラフ構造をファイルにどう保存するのか - 基本的には、固定長のものをバイナリで順に書き込む - 可変長の物は、サイズを書き込んでデータを書き込む - 特定のデータを引っ張ってくるためにoffsetも保存する - 可変長のデータを保存する場合、前から順に読まないと 欲しいデータに到着できないことがあるが、 offsetを保存しておけば、直接データを読めるようになる

13.

hnswのグラフ構造をファイルにどう保存するのか offset level0: 4byte // データ要素において、リンクリストへのoffset max_elements: 4byte // 最大要素数 current_element_count: 4byte // 現在の要素数 size_data_per_element: 4byte // データ要素のメモリサイズ label_offset: 4byte // データ要素において、ラベルへのoffset data_offset: 4byte // データ要素において、データへのoffset max_level: 4byte // インデックスにおける最大level(レイヤー数) enterpoint_node: ? maxM: 4byte // 設定値M maxM0: 4byte // 設定値M0 など

14.

hnswのグラフ構造をファイルにどう保存するのか data_level0_memory: current_element_count * size_data_per_element byte // 可変長 link_lists: current_element_count個 link listsは、level0のみ存在するノードなら、0が書かれ、 複数levelに存在するノードなら、レベル数と、レベル数 * size_links_per_element byte書き込む メモリのみに存在するプログラムであれば、構造体やクラスで考えるだけ ファイルに保存する場合、生存期間がプロセスより長いので、どの様にデータを書き込むか決める必要 がある(C言語だと、構造体の順番によってメモリのレイアウトが変わる)

15.

ファイルにインデックスを保存する際の話 google/codesearch を例にする 可変長なデータから効率的に探索したい(二分探索したい) 課題 - 可変長なデータの場合、素直にサイズとデータを保存すると 先頭から順に見ていかないと、要素を見ていけない

16.

ファイルにインデックスを保存する際の話 例 [“hideno”, “isono”, “kato”, “minami”, “miyazaki”, “nunokawa”, “terai”] ソート済みの↑みたいな要素を探索する場合2分探索できる ファイルにデータを保存する場合 6hideno5isono4kato6minami8miyazaki8nunokawa5terai 二分探索したいけど、i個目の要素が取得できない、、、

17.

ファイルにインデックスを保存する際の話 固定長のインデックスを用意すれば良い 6hideno5isono4kato6minami8miyazaki8nunokawa5terai ↑のデータに対して各要素へのオフセットを保存する [0, 7, 13, 18, 25, 34, 43] i番目のデータを取得したかったら、i番目のoffsetを取得して、offsetでアクセスすれば データが取得できる 二分探索できる

18.

まとめ - hnswの構造は意外と単純 - ファイルに保存する上で可変長なデータの扱いは重要 - hnswlibのコードは読みづらい - index formatのドキュメントとか欲しかった 変数名とか命名規則がバラバラ - 競プロやっててよかった - dijkstraのアルゴリズムがそのまんま出てくる