論文リーディング｜HM-ANN：ANNSがヘテロジニアスメモリに出会うとき
HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogenous Memoryは、2020 Conference on Neural Information Processing Systems (NeurIPS 2020)に採択された研究論文である。本論文では、HM-ANNと呼ばれる、グラフに基づく類似性探索のための新しいアルゴリズムを提案する。このアルゴリズムは、最新のハードウェア環境におけるメモリの不均一性とデータの不均一性の両方を考慮する。HM-ANNは圧縮技術を用いずに、1台のマシンで10億スケールの類似性検索を可能にする。ヘテロジニアスメモリ(HM)は、高速だが小さいダイナミックランダムアクセスメモリ(DRAM)と、低速だが大きいパーシステントメモリ(PMem)の組み合わせを表す。HM-ANNは、特にデータセットがDRAMに収まらない場合に、低い探索レイテンシと高い探索精度を達成する。このアルゴリズムは、最新の近似最近傍(ANN)探索ソリューションに対して明確な優位性を持つ。
動機
ANN検索アルゴリズムは、その登場以来、DRAMの容量が限られているため、クエリの精度とクエリのレイテンシとの間に基本的なトレードオフが存在する。高速なクエリアクセスのためにインデックスをDRAMに格納するためには、データポイント数を制限するか、圧縮されたベクトルを格納する必要がありますが、どちらも検索精度を低下させます。グラフベースのインデックス（HNSW：Hierarchical Navigable Small World）は、クエリ実行時の性能とクエリ精度に優れている。しかし、これらのインデックスは、10億スケールのデータセットで動作する場合、1TiBレベルのDRAMを消費することもある。
億スケールのデータセットを生フォーマットでDRAMに保存させないための回避策は他にもある。データセットが大きすぎて1台のマシンのメモリに収まらない場合、データセットのポイントの積量子化などの圧縮アプローチが使われる。しかし、量子化の際に精度が落ちるため、圧縮されたデータセットを用いたインデックスの再現性は通常低い。Subramanyaら[1]は、ソリッド・ステート・ドライブ（SSD）を活用し、未加工のデータセットをSSDに、圧縮された表現をDRAMに保存するDisk-ANNと呼ばれるアプローチにより、単一マシンで10億スケールのANN検索を実現することを模索している。
ヘテロジニアスメモリ入門
画像名HMxxによるメモリ/ストレージ階層
画像名HMxxによるメモリ/ストレージ階層構造
ソースhttp://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
ヘテロジニアスメモリ(HM)は高速だが小さいDRAMと低速だが大きいPMemの組み合わせを表します。DRAMは、最新のサーバーには必ず搭載されている通常のハードウェアであり、そのアクセスは比較的高速です。Intel® Optane™ DC Persistent Memory Modulesのような新しいPMemテクノロジーは、NANDベースのフラッシュ（SSD）とDRAMのギャップを埋め、I/Oボトルネックを解消します。PMemはSSDのように耐久性があり、メモリのようにCPUから直接アドレス指定が可能です。Renenら[2]は、設定された実験環境において、PMemの読み取り帯域幅はDRAMより2.6倍、書き込み帯域幅は7.5倍低いことを発見しています。
HM-ANN設計
HM-ANNは正確で高速な10億スケールのANN探索アルゴリズムであり、圧縮なしでシングルマシン上で動作する。HM-ANNの設計はHNSWのアイデアを一般化したもので、その階層構造はHMに自然に適合する。HNSWは複数の層から構成され、第0層のみがデータセット全体を含み、残りの各層はその直下の層の要素のサブセットを含む。
3つの階層を持つHNSWの例](https://assets.zilliz.com/2_25a1836e8b.png)
出典https://arxiv.org/pdf/1603.09320.pdf
- データセットのサブセットのみを含む上位レイヤーのエレメントは、ストレージ全体のごく一部を消費する。この観察から、これらの要素はDRAMに配置するのに適した候補となる。このように、HM-ANNの検索の大部分は上位層で行われると予想され、DRAMの高速アクセス特性を最大限に活用することができる。しかし、HNSWの場合、ほとんどの検索は最下層で行われる。
- 最下層はデータセット全体を格納するため、PMemに配置するのに適している。 レイヤ0へのアクセスは低速であるため、各クエリでアクセスされるのはごく一部とし、アクセス頻度を下げることが望ましい。
グラフ構築アルゴリズム
HM-ANNのグラフ構築例](https://assets.zilliz.com/3_dd9627c753.png)
出典http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
HM-ANNの構築の重要な考え方は、レイヤ0での検索に優れたナビゲーションを提供するために、高品質な上位レイヤを作成することです。したがって、ほとんどのメモリアクセスはDRAMで行われ、PMemでのアクセスは減少します。これを可能にするために、HM-ANNの構築アルゴリズムは、トップダウンの挿入フェーズとボトムアップの昇格フェーズを持つ。
トップダウン挿入フェーズでは、最下層のレイヤがPMem上に配置されると、ナビゲート可能なスモールワールドグラフが構築される。
ボトムアップ昇格フェーズでは、最下位レイヤからピボットポイントを昇格させ、精度をあまり落とさずにDRAM上に配置される上位レイヤを形成する。レイヤ0からの要素の高品質な投影がレイヤ1に作成された場合、レイヤ0での検索はわずか数ホップでクエリの正確な最近傍を見つける。
- HNSWのランダム選択による昇格の代わりに、HM-ANNは高次数の昇格戦略を用い、レイヤ0で最も次数の高い要素をレイヤ1に昇格させる。より高いレイヤでは、HM-ANNは昇格率に基づいて高次ノードを上位レイヤに昇格させる。
- HM-ANNは、より多くのノードをレイヤ0からレイヤ1に昇格させ、レイヤ1の各要素の最大隣接数を大きく設定する。上位レイヤのノード数は、使用可能なDRAM容量によって決定されます。レイヤ0はDRAMに保存されないため、DRAMに保存される各レイヤをより密にすることで、探索品質が向上します。
グラフ探索アルゴリズム
HM-ANNのグラフ探索例](https://assets.zilliz.com/4_a5a7f29c93.png)
出典http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
探索アルゴリズムは、高速メモリ探索とプリフェッチによるレイヤ0並列探索の2つのフェーズから構成される。
高速メモリ探索
HNSWと同様に、DRAM内の探索は最上層のエントリポイントから開始し、最上層からレイヤ2まで1-greedy探索を行う。HM-ANNでは、レイヤ0での探索空間を絞り込むために、レイヤ1での探索バジェットを efSearchL1 とし、レイヤ1での候補リストのサイズを制限して探索を行う。HNSWが1つのエントリーポイントしか使用しないのに対し、HM-ANNではレイヤ0とレイヤ1の間のギャップは他の2つのレイヤ間のギャップよりも特別に扱われる。
プリフェッチによるレイヤー0の並列探索
最下層では、HM-ANNは、レイヤ1を検索して得られた前述の候補を均等に分割し、スレッドによる並列マルチスタート1-greedy検索を実行するためのエントリポイントとして見なす。各探索から上位の候補を集め、最良の候補を見つける。周知のように、レイヤ1からレイヤ0に降りることは、まさにPMemに行くことである。 並列探索は、PMemの待ち時間を隠し、メモリ帯域幅を最大限に利用することで、探索時間を増加させることなく探索品質を向上させる。
HM-ANNは、DRAMにソフトウェアで管理されたバッファを実装し、メモリアクセスが発生する前にPMemからデータをプリフェッチする。レイヤ1を検索するとき、HM-ANNは非同期にefSearchL1内の候補の近傍要素とレイヤ1の近傍要素のコネクションをPMemからバッファにコピーする。レイヤ0で検索が行われるとき、アクセスされるデータの一部はすでにDRAMにプリフェッチされているため、PMemにアクセスする待ち時間が隠蔽され、問い合わせ時間の短縮につながる。これは、ほとんどのメモリアクセスがDRAMで行われ、PMemでのメモリアクセスが削減されるというHM-ANNの設計目標に合致している。
評価
本論文では、広範な評価を行った。すべての実験は、Intel Xeon Gold 6252 CPU@2.3GHz を搭載したマシンで行われた。高速メモリとして DDR4 (96GB)、低速メモリとして Optane DC PMM (1.5TB)を使用。5つのデータセットを評価した：BIGANN、DEEP1B、SIFT1M、DEEP1M、GIST1M。億スケールのテストには、以下のスキームが含まれる：億スケールの量子化ベースの手法（IMI+OPQとL&C）、非圧縮ベースの手法（HNSWとNSG）。
億スケールのアルゴリズム比較
表1](https://assets.zilliz.com/5_4297db66a9.png)
表1では、異なるグラフベースのインデックスの構築時間とストレージを比較している。HNSWが最も短い構築時間を要し、HM-ANNはHNSWより8%の追加時間を必要とする。HM-ANNはレイヤー0からレイヤー1へより多くのノードを昇格させるため、全体のストレージ使用量ではHSNWより5～13%大きい。
図1](https://assets.zilliz.com/6_f363e64d3f.png)
図1では、異なるインデックスのクエリー性能を分析している。図1の(a)と(b)は、HM-ANNが1ms以内に95%以上のトップ1リコールを達成していることを示している。図1の(c)と(d)は、HM-ANNが4ms以内に90%以上のトップ100リコールを達成していることを示している。HM-ANNは、他のすべてのアプローチよりも優れた遅延対想起性能を提供する。
ミリオンスケールのアルゴリズム比較
図2](https://assets.zilliz.com/7_a5c23de240.png)
図2では、純粋なDRAM環境において、異なるインデックスのクエリ性能を分析しています。HNSW、NSG、HM-ANNが、DRAMに適合する3つの100万スケールのデータセットで評価されています。HM-ANNは依然としてHNSWよりも優れた問い合わせ性能を達成している。その理由は、HM-ANNの距離計算の総数がHNSW（平均900/クエリ）より少ない（平均850/クエリ）ためである。
高次昇進の効果
図3では、ランダム昇格と高次昇格を同じ構成で比較している。高次プロモーションはベースラインを上回る。高次プロモーションはランダムプロモーションの1.8倍、4.3倍、3.9倍の速さで、それぞれ95%、99%、99.5%の想起目標に到達する。
メモリ管理技術によるパフォーマンス向上
図5は、HNSWとHM-ANNの間の一連のステップを含み、HM-ANNの各最適化がその改善にどのように寄与するかを示している。BPは、インデックスを構築する際のボトムアップ推進を表す。PL0はParallel layer-0探索を表し、DPはPMemからDRAMへのデータプリフェッチを表す。一歩一歩、HM-ANNの検索性能は向上している。
結論
HM-ANNと呼ばれる新しいグラフベースの索引付けと探索アルゴリズムは、グラフベースのANNの階層的設計とHMのメモリヘテロジニアリティをマッピングする。評価は、HM-ANNが10億点データセットにおける新しい最先端インデックスに属することを示している。
我々は、産業界だけでなく学界においても、永続記憶装置上でのインデックス構築が注目されている傾向に注目している。しかし、HM-ANNの構築にはまだ数日かかり、Disk-ANNと比較して大きな差はない。例えば、PMemの粒度(256Byte)を意識し、キャッシュラインをバイパスするためにストリーミング命令を使用するなど、PMemの特性をより注意深く利用することで、HM-ANNの構築時間を最適化することが可能であると考えています。また、耐久性のあるストレージデバイスを用いたアプローチも今後提案されると考えている。
参考文献
[1]:Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy：DiskANN: シングルノード上での高速高精度10億点最近傍探索, NIPS, 2019
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node - Microsoft Research
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
[2]:このような、"nearest-neighbor-search "は、"nearest-neighbor-search "と "nearest-neighbor-search "を組み合わせたものである：永続メモリI/Oプリミティブ, CoRR & DaMoN, 2019
読み続けて
Vector Databases vs. Key-Value Databases
Use a vector database for AI-powered similarity search; use a key-value database for high-throughput, low-latency simple data lookups.
AI Integration in Video Surveillance Tools: Transforming the Industry with Vector Databases
Discover how AI and vector databases are revolutionizing video surveillance with real-time analysis, faster threat detection, and intelligent search capabilities for enhanced security.
Top 5 AI Search Engines to Know in 2025
Discover the top AI-powered search engines of 2025, including OpenAI, Google AI, Bing, Perplexity, and Arc Search. Compare features, strengths, and limitations.