🚀 Zilliz Cloudを無料で試す、完全管理型のMilvus—10倍の高速パフォーマンスを体験しよう！今すぐ試す>>

始める

Home BlogsHNSWlibを始める

HNSWlibを始める

Engineering

November 25, 2024

Haziqa Sajid

セマンティック検索は、機械が言語を理解し、AIやデータ分析に不可欠な、より良い検索結果をもたらすことを可能にする。言語が埋め込みとして表現されると、検索は厳密な方法と近似的な方法を用いて実行することができる。近似最近傍(ANN)検索は、高次元データに対して計算コストのかかる厳密最近傍検索とは異なり、与えられたクエリ点に最も近いデータセット内の点を素早く見つけるために使用される手法である。ANNは近似最近傍探索の結果を提供することで、より高速な検索を可能にする。

近似最近傍(ANN)検索のアルゴリズムの1つにHNSW(Hierarchical Navigable Small Worlds)があり、HNSWlibで実装されています。このブログでは

HNSW アルゴリズムを理解する。
HNSWlib とその主な機能について説明する。
HNSWlibをセットアップし、インデックス構築と検索の実装をカバーする。
Milvusと比較する。

HNSWを理解する

Hierarchical Navigable Small Worlds (HNSW)は、グラフベースのデータ構造で、特に高次元空間において、「スモールワールド」ネットワークの多層グラフを構築することで、効率的な類似検索を可能にする。2016年に発表されたHNSWは、ブルートフォース検索やツリーベース検索のような従来の検索手法に関連するスケーラビリティの問題に対処している。推薦システム、画像認識、検索拡張世代（RAG）など、大規模なデータセットを含むアプリケーションに最適です。

HNSWが重要な理由

HNSWは、高次元空間における最近傍探索の性能を大幅に向上させる。階層構造とスモールワールド・ナビゲータビリティを組み合わせることで、旧来の手法に見られる計算効率の悪さを回避し、巨大で複雑なデータセットでも高い性能を発揮することができる。これをよりよく理解するために、HNSWの仕組みを見てみよう。

HNSWの仕組み

階層的レイヤー：HNSWはデータをレイヤーの階層に整理し、各レイヤーはエッジで接続されたノードを含む。上位のレイヤーは疎であり、地図をズームアウトして都市間の主要な高速道路だけを見るように、グラフを広範囲に「スキップ」することができる。下位のレイヤーは密度が高くなり、より詳細で、より近い隣人同士のつながりを提供する。
ナビゲーバブル・スモール・ワールドのコンセプトHNSWの各レイヤーは、ノード（データポイント）が互いに数ホップしか離れていない「スモールワールド」ネットワークのコンセプトに基づいています。探索アルゴリズムは、最も高密度で疎なレイヤーから開始し、徐々に高密度のレイヤーに移動しながら下へ下へと探索を絞り込んでいく。このアプローチは、グローバルな視野から近隣レベルの詳細へと移動し、検索範囲を徐々に狭めていくようなものだ。

図1：ナビゲート可能なスモールワールドグラフの例

スキップリストのような構造：HNSWの階層的な側面は、スキップリストに似ている。スキップリストは確率的なデータ構造であり、上位の階層ほどノード数が少なくなるため、最初の検索を高速に行うことができる。

図2：スキップリスト構造の例

与えられたスキップリストで96を検索するには、左端のヘッダー・ノードで最上位レベルから始める。右側に移動すると、96より小さい31に遭遇するので、次のノードに進みます。ここで、もう一度31を見つけるために、もう1つ下のレベルに移動します。もう一度31を見つけたら、右に移動し、目標値である96に到達する。こうして、スキップリストの最下層に降りることなく、96を見つけることができる。

探索効率：HNSWアルゴリズムは、最上位レイヤーのエントリー・ノードから開始し、各ステップでより近傍に進む。最も類似したノードが見つかる可能性の高い最下層に到達するまで、各レイヤーを粗視化から細視化探索に使用しながら、レイヤーを下降する。このレイヤー・ナビゲーションは、探索する必要があるノードとエッジの数を減らし、探索を高速かつ正確にします。
挿入とメンテナンス：新しいノードを追加するとき、アルゴリズムは確率に基づいてそのエントリーレイヤーを決定し、近傍選択ヒューリスティックを使用して近くのノードに接続します。このヒューリスティックは接続性を最適化することを目的とし、グラフ密度のバランスをとりながらナビゲーションを向上させるリンクを作成する。このアプローチにより、構造はロバストに保たれ、新しいデータポイントに適応できる。

我々はHNSWアルゴリズムについて基礎的な理解を持っているが、それをゼロから実装することは圧倒的である。幸いなことに、コミュニティはHNSWlibのようなライブラリを開発し、使い方を単純化することで、頭を悩ませることなくアクセスできるようにしている。それでは、HNSWlibを詳しく見ていきましょう。

HNSWlibの概要

HNSWを実装した一般的なライブラリであるHNSWlibは、非常に効率的でスケーラブルであり、数百万点でも十分な性能を発揮します。グラフ層間の素早いジャンプを可能にし、高密度で高次元のデータに対する探索を最適化することで、線形以下の時間複雑性を実現しています。HNSWlib の主な特徴は以下の通り：

グラフベースの構造：多層グラフでデータ点を表現し、高速な最近傍探索を可能にします。
高次元の効率性：高次元データに最適化され、迅速かつ正確な近似検索を実現します。
サブリニア検索時間:階層をスキップすることでサブリニアの複雑さを実現し、速度を大幅に向上。
動的更新：グラフを完全に再構築することなく、ノードの挿入と削除をリアルタイムでサポートします。
メモリ効率：大規模データセットに適した効率的なメモリ使用。
スケーラビリティ数百万データポイントまで拡張可能で、レコメンデーションシステムのような中規模アプリケーションに最適。

注：HNSWlib はベクトル検索アプリケーションの簡単なプロトタイプを作成するのに優れています。しかし、スケーラビリティに限界があるため、数億から数十億のデータポイントを含む複雑なシナリオには、専用のベクトルデータベースなど、より良い選択肢があるかもしれません。それでは実際に見てみよう。

HNSWlib を始める：ステップ・バイ・ステップ・ガイド

このセクションでは、HNSW インデックスを作成し、データを挿入し、検索を実行することで、HNSWlib をベクトル検索ライブラリとして使用する方法を説明します。まずはインストールから始めましょう：

セットアップとインポート

Python で HNSWlib を使い始めるには、まず pip を使ってインストールします：

pip install hnswlib

次に、必要なライブラリをインポートします：

import hnswlib 
import numpy as np

データの準備

この例では、NumPy、10,000個の要素を持つランダムなデータセットを生成する。

dim = 256  # Dimensionality of your vectors
num_elements = 10000  # Number of elements to insert

データを作成しよう：

data = np.random.rand(num_elements, dim).astype(np.float32)  # Example data

データの準備ができたので、インデックスを作成しよう。

インデックスの構築

インデックスを作成するには、ベクトルの次元数と空間タイプを定義する必要があります。インデックスを作成しよう：

p = hnswlib.Index(space='l2', dim=dim)

space='l2':このパラメータは類似度に使用する距離メトリックを定義します。これを'l2' に設定すると、ユークリッド距離（L2ノルム）を使用することになります。代わりに'ip' に設定すると、内積を使用することになり、余弦類似度のようなタスクに役立ちます。

dim=dim:このパラメータは、扱うデータ点の次元を指定します。インデックスに追加するデータの次元と一致していなければなりません。

以下はインデックスを初期化する方法です：

p.init_index(max_elements=num_elements, ef_construction=200, M=16)

max_elements=num_elements:インデックスに追加できる要素の最大数を設定します。Num_elements が最大容量なので、10,000個のデータポイントを扱うため、これを10,000に設定します。

ef_construction=200:このパラメータは、インデックス作成時の精度対作成速度のトレードオフを制御します。高い値を設定するとリコール（精度）が向上しますが、メモリ使用量と構築時間が増加します。一般的な値は100から200です。

M=16:このパラメータは、各データポイントに対して作成される双方向リンクの数を決定し、精度と検索速度に影響を与える。一般的な値は12から48の間で、16が中程度の精度とスピードのバランスになることが多い。

p.set_ef(50)  # This parameter controls the speed/accuracy trade-off

ef:ef パラメーターは "exploration factor"（探索係数）の略で、探索中にどれだけの近傍探索を行うかを決定する。ef の値が高いほど、より多くの近傍探索が行われることになり、一般的に探索の精度（リコール）が上がりますが、探索速度も遅くなります。逆に、ef の値が低いと、検索は速くなりますが、精度が落ちる可能性があります。

この場合、ef を50に設定すると、検索アルゴリズムは最も類似したデータポイントを見つける際に50近傍まで評価します。

注意:ef_construction はインデックス作成時に近傍探索の労力を設定し、精度を向上させますが、作成は遅くなります。ef はクエリ実行時に探索の労力を制御し、各クエリに対して動的に速度と想起のバランスを取ります。

検索の実行

HNSWlibを使って最近傍検索を実行するには、まずランダムなクエリベクトルを作成します。この例では、ベクトルの次元数はインデックスされたデータと一致します。

query_vector = np.random.rand(dim).astype(np.float32)  # Example query

labels, distances = p.knn_query(query_vector, k=5)  # k is the number of nearest neighbors

query_vector:この行は、インデックス付けされたデータと同じ次元数のランダムなベクトルを生成し、最近傍検索の互換性を確保します。
knn_query:このメソッドは，インデックスp 内でquery_vector のk 最近傍を探索します．このメソッドは，2つの配列を返します．labelsこの配列は，最近傍のインデックスを含み，distances は，クエリベクトルから各近傍への距離を表します．ここで、k=5 は、最も近い5つの近傍を見つけることを指定します。

ラベルと距離を表示した結果がこれです：

print("Nearest neighbors' labels:", labels)
print("Distances:", distances)

> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718    35.484592 35.627766 35.828312 35.91495 ]]

HNSWlib を使い始めるための簡単なガイドです。

前述したように、HNSWlib はプロトタイピングや中規模データセットの実験に最適なベクトル検索エンジンです。より高いスケーラビリティが必要な場合や、エンタープライズレベルの機能が必要な場合は、オープンソースのMilvusや、Zilliz Cloudのフルマネージドサービスのような、専用のベクターデータベースを選択する必要があるかもしれません。そこで、次のセクションでは、HNSWlib と Milvus を比較します。

HNSWlib と Milvus のような汎用ベクターデータベースの比較

ベクトル・データベースは、データを数学的表現として保存し、機械学習モデルによる検索、レコメンデーション、テキスト生成を可能にします。

HNSWlibのようなベクトル指標ライブラリは、ベクトル検索と取得を向上させますが、完全なデータベースの管理機能はありません。一方、milvusのようなベクトルデータベースは、大規模なベクトル埋め込みを扱うように設計されており、データ管理、インデックス作成、クエリ機能において、スタンドアロンライブラリには通常ない利点を提供します。Milvusを使用するその他の利点は以下の通りです：

高速ベクトル類似検索：Milvusは、画像検索、推薦システム、自然言語処理(NLP)、検索拡張世代(RAG)などのアプリケーションに理想的な、10億スケールのベクトルデータセットに対してミリ秒レベルの検索性能を提供します。
スケーラビリティと高可用性：大量のデータを処理するために構築されたMilvusは、水平方向に拡張可能で、信頼性のためのレプリケーションとフェイルオーバーメカニズムを備えています。
分散アーキテクチャMilvusは、ストレージとコンピューティングを複数のノードに分離した分散型のスケーラブルなアーキテクチャを採用しており、柔軟性と堅牢性を実現しています。
ハイブリッド検索：Milvusは、マルチモーダル検索、ハイブリッドスパース検索、ハイブリッドデンス検索、ハイブリッドフルテキスト検索をサポートし、多様で柔軟な検索機能を提供します。
柔軟なデータサポートMilvusはベクトル、スカラー、構造化データなど様々なデータタイプをサポートし、単一のシステム内でシームレスな管理と分析を可能にします。
活発な コミュニティとサポート活発なコミュニティが定期的なアップデート、チュートリアル、サポートを提供し、Milvusがユーザーのニーズとこの分野の進歩に常に合致していることを保証します。
AIとの統合：Milvusは、様々な一般的なAIフレームワークやテクノロジーと統合されており、開発者は使い慣れた技術スタックでアプリケーションを簡単に構築することができます。

また、MilvusはZiliz Cloud上でフルマネージドサービスを提供しており、手間がかからず、Milvusの10倍の速さで利用できる。

比較MilvusとHNSWlibの比較

特徴	Milvus	HNSWlib
スケーラビリティ	数十億のベクトルを簡単に処理	RAM 使用量のため、より小さなデータセットに最適
理想的な用途	プロトタイピング，実験，企業レベルのアプリケーション	プロトタイプと軽量のANNタスクに特化
インデックス作成	HNSW、DiskANN、量子化、バイナリなど10以上のインデックス作成アルゴリズムをサポート	グラフベースのHNSWのみを使用
統合	APIとクラウドネイティブサービスを提供	軽量なスタンドアロンライブラリとして機能
パフォーマンス	大規模データ、分散クエリに最適化	高速だがスケーラビリティは限定的

全体として、Milvusは複雑なインデックス作成が必要な大規模なプロダクショングレードのアプリケーションに適しており、HNSWlibはプロトタイピングやより単純なユースケースに適している。

結論

セマンティック検索はリソースを大量に消費するため、HNSW が行うような内部データ構造化は、データ検索を高速化するために不可欠である。HNSWlibのようなライブラリは実装に気を配っているので、開発者はベクター機能をプロトタイプするためのレシピを用意している。わずか数行のコードで、独自のインデックスを構築し、検索を実行できる。

HNSWlibは手始めとして最適です。しかし、複雑で量産可能なAIアプリケーションを構築したいのであれば、専用のベクターデータベースが最適だ。例えば、Milvusはオープンソースのベクターデータベースで、高速なベクター検索、スケーラビリティ、可用性、データ型やプログラミング言語の柔軟性など、多くのエンタープライズ対応機能を備えている。