Pinecone (ベクトル DB) はなぜ 100 万件のベクトルを 10ms で検索できるか? BigQuery の COUNT(DISTINCT) は 1 兆件のユニーク数を 1% 誤差で 16KB のメモリで返す のはなぜか? Notion / Figma が「リアルタイム同時編集」できる仕組みは何か?
答えはすべて 古典的な「正確で重い」アルゴリズムではなく、「確率的・近似・分散」な現代アルゴリズム。本シリーズでは、実システムで使われている計算手法 を、Python サンプル + ベンチマーク + 採用事例で深掘りします。
1. 「教科書のアルゴリズム」と「実システム」のギャップ
| 問題 | 教科書解 | 現代の実装 |
|---|---|---|
| 1 兆件の COUNT(DISTINCT) | ハッシュセットで重複除去 (O(n) メモリ) | HyperLogLog (16KB で 1% 誤差) |
| 100 万件の最近傍探索 | 全件距離計算 (O(n)) | HNSW (O(log n)、99% Recall) |
| 100 万件中の上位 K 頻度 | ハッシュテーブルで集計 | Count-Min Sketch (省メモリ近似) |
| 「この URL は犯罪サイト?」判定 | DB 全件検索 | Bloom Filter (キャッシュ前段で 99% 即答) |
| 「似てる文書」検出 1 億件 | ペアワイズ全比較 (O(n²)) | MinHash + LSH (O(n)) |
| 3 サーバの分散合意 | (理論研究) | Raft (etcd / Consul で実装) |
| git のコミット改ざん検知 | 全コミット再ハッシュ | Merkle Tree (差分のみ) |
2. 本シリーズで扱うアルゴリズム (15 EP 構想)
- 1EP.01 はじめに (本記事)
- 2EP.02 HNSW — Pinecone / Qdrant / pgvector のベクトル検索
- 3EP.03 HyperLogLog — BigQuery COUNT(DISTINCT)、1 兆件を 16KB
- 4EP.04 Count-Min Sketch — リアルタイムランキング
- 5EP.05 Bloom Filter — キャッシュ・SPV 検証
- 6EP.06 MinHash + LSH — 類似文書検出
- 7EP.07 CRDT — Notion / Figma の同時編集
- 8EP.08 Raft — 分散合意 (etcd / Consul / TiKV)
- 9EP.09 Merkle Tree — git / Bitcoin / IPFS
- 10EP.10 PageRank — Google 検索ランキング
- 11EP.11 Reservoir Sampling — 流れるデータからランダム k 件
- 12EP.12 Skip List — Redis sorted set
- 13EP.13 LSM Tree — RocksDB / Cassandra の書込み
- 14EP.14 MCTS — AlphaGo の探索
- 15EP.15 Self-Attention — Transformer / ChatGPT
3. 各 EP の構成
- 「これで何が動いているか」: Pinecone / Notion / Bitcoin 等の現代事例
- 仕組みのざっくり: 図解と直感的説明
- Python 実装: 30-50 行、教育用ピュア実装
- 実用ライブラリ: hnswlib / datasketch / numpy 等を使った版
- ベンチマーク: 素朴 vs 最適化を計測比較
- メリデメ: いつ使うか、いつ使わないか
- 代替アルゴリズム: 比較選択の指針
- 関連 OSS / 製品: 採用例
4. 読み方の推奨
- 順番に読まなくて OK: EP 間の前提を最小化
- Python は Google Colab で実行: ローカル不要
- 実用ライブラリを試す: 「動かしたい」「業務で使いたい」が動機なら
- 論文を併読: 理論を深掘りしたい人は元論文へのリンクも
- コミュニティで議論: 業務での使用例を共有
5. 前提知識
- Python: 基本構文 + クラス + 内包表記
- 計算量 (O 記法): O(1) / O(log n) / O(n) の感覚
- ハッシュ関数 / SHA-256: 何ができるかは知っている (中身は不要)
- 確率の基本: 期待値・分散の概念
- データ構造: 配列・ハッシュテーブル・ツリーの基本
前提が不安なら
CS 基礎ハンドブック EP.08 (データ構造) と EP.09 (アルゴリズム) を先に読むと、本シリーズの理解が一気に深まります。
6. 次の話
EP.02 では HNSW (Hierarchical Navigable Small World) を扱います。Pinecone / Qdrant / pgvector / OpenSearch の中で動いている、ベクトル検索の主役。Python サンプル + hnswlib ライブラリのベンチマーク付き。
この記事の感想を教えてください
あなたの 1 クリックで、本当にこの記事は更新されます。「もっと詳しく」「続編希望」が一定数集まった記事は、 ふくふくが 実際に内容を拡充したり続編記事を公開 します。 送信したリアクションはお使いのブラウザに記録され、再カウントされません。