近似最近傍探索（ANN: Approximate Nearest Neighbor）は、大規模データから類似したアイテムを高速に検索するための技術です。
画像検索、推薦システム、AIアプリケーションなど、現代の様々なサービスを支える基盤技術となっています。
この記事では、ANNの基本から実装方法まで詳しく解説します。
ANNとは
基本的な定義
近似最近傍探索（Approximate Nearest Neighbor Search）は、与えられたクエリポイントに「非常に近い」ポイントをデータセットから高速に見つける手法です。
英語表記:
- ANN: Approximate Nearest Neighbor
- ANNS: Approximate Nearest Neighbor Search
KNN（厳密最近傍探索）との違い
KNN（K-Nearest Neighbor / 厳密最近傍探索）:
- データセット内の「厳密に」最も近いK個のポイントを探す
- すべてのデータポイントとの距離を計算する必要がある
- 小規模データには適している
- 計算量がデータ数に比例してれる（O(N)）
ANN（近似最近傍探索）:
- 「厳密に」最も近いとは限らないが、「十分に近い」ポイントを探す
- すべてのデータポイントを調べる必要がない
- 大規模データでも高速に動作
- 計算量が大幅に削減される（アルゴリズムによりO(log N)など）
なぜANNが必要か
次元の呪い（Curse of Dimensionality）:
高次元データでは、KNNの計算コストが爆発的に増加します。
具体例:
- データ数:1億個
- 次元数:128次元（画像の特徴ベクトルなど）
- KNNの場合:すべてのポイントとの距離計算が必要 → 実用的でない
- ANNの場合:インデックスを利用して高速検索 → ミリ秒単位で検索可能
トレードオフ
ANNでは以下の3つの要素のバランスを取ります:
- 速度（Speed）:検索にかかる時間
- 精度（Accuracy/Recall）:正しい最近傍を見つけられる確率
- メモリ（Memory）:インデックスが使用するメモリ量
ANNの仕組み
基本的なアプローチ
ANNは主に以下の3つのカテゴリに分類されます:
1. ハッシュベース（Hashing-based）:
局所性鋭敏ハッシュ（LSH）など
2. ツリーベース（Tree-based）:
KD木、ランダム射影木など
3. グラフベース（Graph-based）:
HNSW、NSWなど
メトリック空間
ANNはメトリック空間上で動作します。
主な距離関数:
- ユークリッド距離（L2距離）:点間の直線距離
- コサイン類似度:ベクトルの方向の類似度
- マンハッタン距離（L1距離）:座標の差の絶対値の和
- 内積（Inner Product）:ベクトルの内積
インデックス構築
ANNの基本的な流れ:
- データの前処理:ベクトルの正規化、次元削減など
- インデックス構築:効率的な検索を可能にするデータ構造を作成
- クエリ実行:インデックスを使って高速検索
主要なANNアルゴリズム
1. HNSW（Hierarchical Navigable Small World）
概要:
階層的なグラフ構造を使った最先端のANNアルゴリズム
特徴:
- グラフベースのアプローチ
- スキップリストに似た階層構造
- 検索速度が非常に速い（対数時間複雑度）
- 高い精度を維持
- 現在最も人気のあるANNアルゴリズムの一つ
計算量:
- 構築:O(N log N)
- 検索:O(log N)
仕組み:
- データポイントを複数の層に配置（指数減衰確率で層を決定）
- 上位層から下位層へと階層的に探索
- 各層でグラフをナビゲートして最近傍候補を見つける
利点:
- 非常に高速な検索
- 高い精度
- 動的な追加・削除が可能
欠点:
- メモリ消費が大きい
- インデックス構築に時間がかかる
利用例:
- Faiss
- hnswlib
- NMSLIB
- Milvus、Weaviate、Qdrantなど多くのベクトルデータベース
2. LSH（Locality-Sensitive Hashing / 局所性鋭敏ハッシュ）
概要:
類似したアイテムを同じバケツにハッシュする手法
特徴:
- ハッシュベースのアプローチ
- 類似したベクトルが高確率で同じハッシュ値になる
- 次元数に依存しない計算時間
計算量:
- 検索:O(n^(1/ρ))、ρは1未満の係数
仕組み:
- 複数のハッシュ関数を用意
- 各データポイントをハッシュしてバケツに分類
- クエリをハッシュして該当バケツ内を検索
利点:
- 非常に高次元のデータに有効
- 実装がシンプル
- スケーラブル
欠点:
- 精度がやや低い
- パラメータ調整が難しい
- 偽陽性（False Positives）が発生する可能性
実装例:
- FALCONN
- Faiss（IndexLSH）
3. IVF（Inverted File Index）
概要:
データをクラスタに分割して検索空間を削減
特徴:
- クラスタリングベースのアプローチ
- k-meansなどでデータを分割
- PQ（Product Quantization）と組み合わせることが多い
計算量:
- 検索:O(√N)（クラスタ数を適切に選んだ場合）
仕組み:
- k-meansでデータをクラスタに分割
- クエリに最も近いクラスタを特定
- そのクラスタ内でのみ検索
利点:
- 精度と速度のバランスが良い
- PQと組み合わせてメモリ効率を改善可能
欠点:
- クラスタリングに時間がかかる
- クラスタ境界付近の精度が低下
実装例:
- Faiss（IndexIVFFlat、IndexIVFPQ）
4. PQ（Product Quantization）
概要:
ベクトルを圧縮してメモリ使用量を削減
特徴:
- ベクトル量子化による圧縮
- ベクトルを複数のサブベクトルに分割して量子化
- IVFと組み合わせて使われることが多い
利点:
- メモリ使用量を大幅に削減（元のサイズの1/32など）
- 大規模データセットに適している
欠点:
- 精度が低下
- 圧縮により情報が失われる
実装例:
- Faiss（IndexPQ、IndexIVFPQ）
5. Annoy（Approximate Nearest Neighbors Oh Yeah）
概要:
ツリーベースのシンプルなANNライブラリ
特徴:
- ランダム射影木を複数構築
- メモリマップファイルに対応
- 実装がシンプル
仕組み:
- ランダムに2点を選びハイパープレーンで空間を分割
- 再帰的に分割してツリーを構築
- 複数のツリーを作成（森）
- 検索時に複数のツリーを走査
利点:
- シンプルで使いやすい
- mmapで複数プロセスから読める
- メモリ効率が良い
欠点:
- HNSWやNMSLIBより精度・速度で劣る
- インデックス構築後の追加ができない
開発元:
Spotify
主要なANNライブラリ
1. Faiss（Facebook AI Similarity Search）
開発元:
Meta（旧Facebook）
特徴:
- 最も人気のあるANNライブラリ
- CPU/GPU両対応
- 豊富なアルゴリズム実装（HNSW、IVF、PQ、LSHなど）
- C++実装、Pythonバインディング
インストール:
# CPU版
pip install faiss-cpu
# GPU版
pip install faiss-gpu基本的な使い方:
import faiss
import numpy as np
# データ準備
dimension = 128
database_size = 10000
query_size = 1
# ランダムデータ生成
database_vectors = np.random.random((database_size, dimension)).astype('float32')
query_vectors = np.random.random((query_size, dimension)).astype('float32')
# インデックス構築（L2距離）
index = faiss.IndexFlatL2(dimension)
index.add(database_vectors)
# 検索（上位5件）
k = 5
distances, indices = index.search(query_vectors, k)
print("最近傍のインデックス:", indices)
print("距離:", distances)HNSWの例:
import faiss
# HNSWインデックス作成
# M: 各ノードの接続数（デフォルト32）
# efConstruction: 構築時の探索範囲（デフォルト40）
index = faiss.IndexHNSWFlat(dimension, 32)
index.hnsw.efConstruction = 40
# データ追加
index.add(database_vectors)
# 検索時のパラメータ
index.hnsw.efSearch = 16 # 検索範囲（大きいほど精度向上、速度低下）
# 検索
distances, indices = index.search(query_vectors, k)IVFPQの例:
# クラスタ数
nlist = 100
# PQのサブベクトル数
m = 8
# 各サブベクトルのビット数
nbits = 8
# 量子化器
quantizer = faiss.IndexFlatL2(dimension)
# IVFPQ インデックス
index = faiss.IndexIVFPQ(quantizer, dimension, nlist, m, nbits)
# 訓練（クラスタリング）
index.train(database_vectors)
# データ追加
index.add(database_vectors)
# 検索するクラスタ数
index.nprobe = 10
# 検索
distances, indices = index.search(query_vectors, k)2. Annoy
開発元:
Spotify
インストール:
pip install annoy使い方:
from annoy import AnnoyIndex
# インデックス作成
# 第1引数: 次元数
# 第2引数: 距離メトリック（'angular', 'euclidean', 'manhattan', 'hamming', 'dot'）
index = AnnoyIndex(dimension, 'angular')
# データ追加
for i, vec in enumerate(database_vectors):
index.add_item(i, vec)
# インデックス構築
# 引数: ツリーの数（多いほど精度向上、メモリ増加）
n_trees = 10
index.build(n_trees)
# 保存
index.save('index.ann')
# 読み込み
index = AnnoyIndex(dimension, 'angular')
index.load('index.ann')
# 検索
indices, distances = index.get_nns_by_vector(query_vectors[0], k, include_distances=True)
print("最近傍:", indices)
print("距離:", distances)3. NMSLIB（Non-Metric Space Library）
特徴:
- 高速なHNSW実装
- 様々な距離メトリックに対応
- マルチスレッド対応
インストール:
pip install nmslib使い方:
import nmslib
# インデックス作成
# method: 'hnsw'など
# space: 'cosinesimil', 'l2'など
index = nmslib.init(method='hnsw', space='cosinesimil')
# データ追加
index.addDataPointBatch(database_vectors)
# インデックス構築
index.createIndex({'post': 2}, print_progress=True)
# 1件ずつ検索
ids, distances = index.knnQuery(query_vectors[0], k=k)
print("最近傍ID:", ids)
print("距離:", distances)
# バッチ検索（マルチスレッド）
neighbours = index.knnQueryBatch(query_vectors, k=k, num_threads=4)4. hnswlib
特徴:
- HNSW専用の高速実装
- C++実装、Pythonバインディング
- シンプルで使いやすい
インストール:
pip install hnswlib使い方:
import hnswlib
# インデックス作成
index = hnswlib.Index(space='l2', dim=dimension)
# パラメータ設定
# max_elements: 最大要素数
# ef_construction: 構築時の探索範囲
# M: 接続数
index.init_index(max_elements=database_size, ef_construction=200, M=16)
# データ追加
index.add_items(database_vectors, np.arange(database_size))
# 検索パラメータ
index.set_ef(50) # 検索範囲
# 検索
labels, distances = index.knn_query(query_vectors, k=k)
print("最近傍:", labels)
print("距離:", distances)5. ScaNN（Scalable Nearest Neighbors）
開発元:
Google Research
特徴:
- 最先端の性能
- 大規模データセットに最適化
- 量子化とハイブリッドアプローチ
インストール:
pip install scannライブラリの選び方
データ規模別
小規模（〜100万件）:
- Faiss（IndexFlatL2）
- Annoy
中規模（100万〜1000万件）:
- Faiss（IndexHNSWFlat）
- NMSLIB（HNSW）
- hnswlib
大規模（1000万件以上）:
- Faiss（IndexIVFPQ、GPU版）
- ScaNN
用途別
リアルタイム検索:
- HNSW系（Faiss、hnswlib、NMSLIB）
バッチ処理:
- Faiss（GPU版）
メモリ制約あり:
- Faiss（IndexIVFPQ）
- Annoy
動的更新が必要:
- HNSW系（追加・削除が可能）
- Annoyは再構築が必要
ANNの応用例
1. 画像検索
用途:
類似画像の検索
仕組み:
- CNNなどで画像を特徴ベクトルに変換
- ANNで類似ベクトルを検索
- 対応する画像を返す
例:
- Google画像検索
- 商品画像検索
2. 推薦システム
用途:
ユーザーやアイテムの類似性に基づく推薦
仕組み:
- ユーザー・アイテムをベクトル化（協調フィルタリング、埋め込みなど）
- ANNで類似ユーザー/アイテムを検索
- 推薦リストを生成
例:
- Spotify（音楽推薦）
- Netflix（映画推薦）
- Amazonの商品推薦
3. RAG（Retrieval-Augmented Generation）
用途:
LLMの知識を外部データで補強
仕組み:
- ドキュメントをチャンクに分割し、埋め込みベクトル化
- ユーザーのクエリをベクトル化
- ANNで関連ドキュメントを検索
- LLMに検索結果とクエリを渡して回答生成
例:
- ChatGPT Enterprise
- Claude Projects
- 企業のナレッジベース検索
4. 自然言語処理（NLP）
用途:
- 文書の類似検索
- 意味的検索
- 重複検出
仕組み:
- BERTなどで文をベクトル化
- ANNで類似文を検索
例:
- セマンティック検索
- プラジャリズム検出
- Q&Aシステム
5. 音声・動画検索
用途:
類似音声・動画の検索
仕組み:
- 音声・動画を特徴ベクトルに変換
- ANNで類似コンテンツを検索
例:
- Shazam（音楽識別）
- YouTube関連動画推薦
6. 異常検知
用途:
正常データと異なるパターンの検出
仕組み:
- 正常データの特徴ベクトルを構築
- 新規データと最近傍の距離を計算
- 距離が閾値以上なら異常と判定
例:
- 不正取引検出
- システム異常監視
- 製品の品質管理
ベクトルデータベースとの関係
ベクトルデータベースとは
ANNを内部で使用し、大規模ベクトルデータの保存・検索に特化したデータベース
主なベクトルデータベース:
- Pinecone:マネージドサービス、HNSW使用
- Milvus:オープンソース、Faissベース
- Weaviate:オープンソース、HNSW使用
- Qdrant:オープンソース、HNSW使用
- Chroma:オープンソース、軽量
- Faiss:ライブラリだがベクトルDB的に使える
ベクトルDBが提供する機能
ANNライブラリを超える機能:
- 永続化:ディスクへの保存
- スケーリング:分散処理、シャーディング
- メタデータフィルタリング:属性による絞り込み
- CRUD操作:追加・更新・削除
- API:RESTful API、gRPC
- ハイブリッド検索:キーワード検索とベクトル検索の組み合わせ
パフォーマンスの評価指標
Recall（再現率）
正しい最近傍を見つけられた割合
Recall = (正しく見つけた最近傍の数) / k目標:
通常95%以上を目指す
QPS（Queries Per Second）
1秒あたりに処理できるクエリ数
レイテンシ（Latency）
1クエリの処理時間
メモリ使用量
インデックスが使用するメモリ
インデックス構築時間
インデックス作成にかかる時間
ベンチマーク
ann-benchmarks
ANNアルゴリズムの標準的なベンチマーク
URL:
GitHub - erikbern/ann-benchmarks: Benchmarks of approximate nearest neighbor libraries in Python
Benchmarks of approximate nearest neighbor libraries in Python - erikbern/ann-benchmarks
github.com
評価軸:
- Recall vs QPS（精度と速度のトレードオフ）
- 様々なデータセット（SIFT、GloVe、Wikipediaなど）
結果の見方:
グラフの右上が理想（高精度・高速）
主な結果（2024年時点）
上位アルゴリズム:
- HNSW（hnswlib、Faiss、NMSLIB）
- ScaNN
- Faiss（IVF系）
実装のベストプラクティス
1. データの前処理
正規化:
# L2正規化
import numpy as np
def normalize(vectors):
return vectors / np.linalg.norm(vectors, axis=1, keepdims=True)
normalized_vectors = normalize(database_vectors)次元削減:
高次元（1000次元以上）の場合、PCAで100〜128次元に削減することが多い
from sklearn.decomposition import PCA
pca = PCA(n_components=128)
reduced_vectors = pca.fit_transform(high_dim_vectors)2. パラメータチューニング
HNSW:
M:16〜64（大きいほど精度向上、メモリ増加）efConstruction:100〜200（大きいほど精度向上、構築時間増加）efSearch:50〜500（大きいほど精度向上、検索時間増加）
IVF:
nlist:√N 〜 4√N（クラスタ数）nprobe:1〜nlist（検索するクラスタ数、大きいほど精度向上）
3. 精度と速度のバランス
開発フロー:
- まず精度優先でパラメータ設定
- Recallが目標値（95%など）に達したらパラメータを調整して速度改善
- ベンチマークで性能評価
4. メモリ管理
大規模データの場合:
- PQで圧縮
- ディスクベースのインデックス（Faiss IndexIVF with on-disk storage）
- 分散処理（ベクトルDBを使用）
よくある質問
Q1:ANNとKNNはどう使い分けますか?
A:データ規模で判断します:
- 小規模（〜10万件）:KNNでも十分高速
- 大規模（10万件以上）:ANN推奨
- 厳密な最近傍が必要な場合:KNN
Q2:どのアルゴリズムを選べばいいですか?
A:現在（2024-2025年）のおすすめ:
- まずHNSW（hnswlib、Faiss、NMSLIB）を試す
- メモリが足りない場合:IVFPQまたはPQ
- 超大規模:ScaNNまたはベクトルDB
Q3:精度が低い場合の対処法は?
A:以下を試してください:
- パラメータを調整（efSearch、nprobeなど増やす）
- 別のアルゴリズムを試す
- データの前処理（正規化、次元削減）を見直す
- インデックス構築パラメータを上げる
Q4:動的にデータを追加・削除できますか?
A:アルゴリズムによります:
- HNSW:可能（効率的）
- Annoy:不可（再構築が必要）
- IVF:可能だが再トレーニング推奨
- ベクトルDB:通常サポート
Q5:GPUは使うべきですか?
A:データ規模次第:
- 1000万件以上:GPU版Faiss推奨
- バッチ処理:GPU有効
- リアルタイム検索:CPU版HNSWで十分なことが多い
Q6:どの距離関数を使えばいいですか?
A:用途による:
- 画像・一般的なベクトル:L2（ユークリッド距離）
- テキスト埋め込み:コサイン類似度
- 推薦システム:内積
まとめ
ANN（近似最近傍探索）は、大規模データから類似アイテムを高速に検索するための重要な技術です。
重要なポイント:
- 目的:厳密な最近傍ではなく、十分に近いポイントを高速に見つける
- トレードオフ:速度・精度・メモリのバランスを取る
- 主要アルゴリズム:HNSW、LSH、IVF、PQなど
- 推奨ライブラリ:Faiss、hnswlib、NMSLIB
- 応用:画像検索、推薦システム、RAG、NLPなど
- 選択基準:データ規模、精度要件、メモリ制約で決定
はじめる場合の推奨:
- 小規模データ:Annoyで試す（シンプル）
- 中〜大規模:hnswlibまたはFaiss HNSWから始める
- 本番環境:ベクトルDBの使用を検討
最新動向:
- HNSWが事実上の標準アルゴリズムに
- ベクトルデータベースの急速な発展
- LLMの普及によりRAG用途で需要急増
- GPU対応の進化
ANNは現代のAIアプリケーションを支える基盤技術であり、適切に実装することで大規模データからの高速検索を実現できます。
参考情報
論文:
- HNSW原論文（2016） – Yu. A. Malkov et al.
- Product Quantization（2011） – H. Jégou et al.
ライブラリ:
ベンチマーク:
チュートリアル:
コメント