HNSW：Pinecone・Qdrant・pgvector を 100 倍速くする近似最近傍探索

ChatGPT の RAG、Spotify の楽曲推薦、Google Photos の類似画像検索、メルカリの「似てる商品」。これらすべて 「ベクトル空間でのある点に近い K 個を高速に見つける」 問題。古典的なアプローチは全件距離計算 (O(n))、しかし 100 万件超だと数秒かかる。これを 10ms 以下 にするのが HNSW。

1. これで何が動いているか

• Pinecone (ベクトル DB SaaS): HNSW を中核アルゴリズムとして採用
• Qdrant: HNSW (デフォルト)、Rust で実装
• pgvector (PostgreSQL 拡張): HNSW インデックス
• OpenSearch / Elasticsearch: HNSW (Lucene 9 から)
• Weaviate: HNSW
• Milvus: HNSW + IVF + PQ のハイブリッド
• FAISS (Meta): HNSW を含む複数アルゴリズム

2. 仕組みのざっくり

• スモールワールドグラフ: ランダムだけど「6 次の隔たり」のように頂点間距離が短いグラフ
• 階層化: 上位層は疎、下位層は密。上から大まかに探索 → 下で詳細に
• 確率的レベル: 各点を確率的に複数階層に配置 (上位ほど少数)
• Greedy 探索: 各層で「現在地から最も近い隣接ノード」に進む
• ef パラメータ: 探索時の候補リスト幅、大きいほど精度↑速度↓

3. Python サンプル: hnswlib (実用ライブラリ)

# pip install hnswlib numpyimport numpy as npimport hnswlibimport time
# 5 万件の 128 次元ベクトルnp.random.seed(42)N, D = 50_000, 128data = np.random.randn(N, D).astype('float32')queries = np.random.randn(10, D).astype('float32')
# HNSW インデックス構築hnsw = hnswlib.Index(space='l2', dim=D)hnsw.init_index(max_elements=N, ef_construction=400, M=32)hnsw.add_items(data, np.arange(N))hnsw.set_ef(200)  # 検索時の探索幅
# HNSW 検索start = time.time()labels_hnsw, distances_hnsw = hnsw.knn_query(queries, k=10)hnsw_time = time.time() - start
# ブルートフォース検索 (比較用)start = time.time()brute_results = []for q in queries:    dists = np.linalg.norm(data - q, axis=1)    idx = np.argsort(dists)[:10]    brute_results.append(idx)brute_time = time.time() - start
# Recall 計算recalls = []for i in range(len(queries)):    correct = len(set(labels_hnsw[i]) & set(brute_results[i]))    recalls.append(correct / 10)
print(f"HNSW: {hnsw_time*1000:.2f} ms (10 クエリ)")print(f"Brute-force: {brute_time*1000:.2f} ms (10 クエリ)")print(f"Speedup: {brute_time/hnsw_time:.1f}x")print(f"Recall@10: {np.mean(recalls)*100:.1f}%")
# 実行結果 (M1 Mac で確認):# HNSW: 6.30 ms# Brute-force: 92.66 ms# Speedup: 14.7x# Recall@10: 95.0%

4. パラメータの効果

5. メリットとデメリット

6. 代替アルゴリズム

• IVF (Inverted File Index): クラスタリングで候補絞込み、HNSW より低精度だが省メモリ
• PQ (Product Quantization): ベクトル圧縮、メモリ削減 8-32 倍
• ScaNN (Google): 大規模向け、Meta の SCANN ライブラリ
• Annoy (Spotify): ランダム射影木、シンプルで実装軽量
• FAISS (Meta): 上記すべてを統合した最強ライブラリ

7. 業務での選び方

8. 関連 OSS / 製品

• hnswlib (https://github.com/nmslib/hnswlib): C++ + Python ラッパー、デファクト
• Pinecone (https://www.pinecone.io/): マネージド・ベクトル DB
• Qdrant (https://qdrant.tech/): OSS Rust 製
• pgvector (https://github.com/pgvector/pgvector): PostgreSQL 拡張
• FAISS (https://github.com/facebookresearch/faiss): Meta 製、研究向け

9. 参考論文

• Malkov & Yashunin (2018) "Efficient and robust approximate nearest neighbor search using HNSW" — 元論文
• Aumüller et al. (2020) "ANN-Benchmarks" — 各種アルゴリズムのベンチマーク

10. 次の話

EP.03 では HyperLogLog を扱います。BigQuery の COUNT(DISTINCT) を 1 兆件 16KB で 1% 誤差で実現する確率的アルゴリズム。Python 実装で 1.01% の誤差を確認します。