HNSWの内部構造

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

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

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

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

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

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

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

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する

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

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している

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

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

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 など

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言語だと、構造体の順番によってメモリのレイアウトが変わる)

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

• https://github.com/google/codesearch/blob/master/index/read.go

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

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

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