Image Vector PoC: Voronoi分割によるFirestoreのベクトル検索最適化

本日は Image Vector PoC プロジェクトにおける技術的なブレイクスルーについて報告します。 Firestore を利用したベクトル検索において、Voronoi（ボロノイ）分割を用いた事前フィルタリングを導入し、検索コストとパフォーマンスを劇的に改善することに成功しました。

背景：Firestore ベクトル検索の課題

このプロジェクトでは、顔認識モデル（512-D ArcFace embedding）を用いた画像検索システムを構築しています。バックエンドとして Google Firestore のベクトル検索機能を利用していますが、いくつかの課題に直面していました。

Firestore のベクトル検索は Exact KNN (厳密なK近傍法) を採用しており、ANN（近似最近傍探索）ではありません。これは精度が高い反面、フィルタリングを行わない場合、コレクション内の全ドキュメントをスキャンする必要があります。

Firestore の課金体系において、ベクトル検索のコストはスキャンしたドキュメント数に応じた Read コスト（1ベクトルにつき1/100Read相当）が発生します。今回のデータセットは約 70,000 件の顔ベクトルを含んでおり、単純な検索を行うと 1回あたり 700 read が発生することになります。 Firestore の無料枠は 1日あたり 50,000 read ですので、約72回検索しただけで無料枠を超過してしまいます。開発中のテストや、少人数の内部利用であっても、これは無視できないコストとなります。

解決策：Voronoi 分割による事前フィルタリング

この課題を解決するために、Voronoi 分割（Voronoi Partitioning） を用いた事前フィルタリングを導入しました。具体的な手法としては、データセット全体を代表する 256 個のセントロイド（重心）を K-Means 等で事前に計算し、各画像ベクトルがどの Voronoi 領域に属するかを求めます。

今回の実装では、各画像ベクトルに対して 最も近い 2つの Voronoi 領域（256クラスのうちの上位2つのID） を付与し、クエリ時には同様にクエリベクトルに近い領域だけでフィルタリングを行いました。

実験とその成果

技術的な詳細や実験過程は以下の Notebook で公開しています。

このアプローチにより、以下の成果が得られました。

検索対象の削減: 事前に Voronoi 領域でフィルタリングすることで、検索対象を全体の約 5% 程度に絞り込むことができました。
コスト削減 & 高速化: スキャンするドキュメント数が激減したため、Firestore の Read コストが大幅に下がり、検索スピードも向上しました。

なぜうまくいったのか？

今回の成功要因として、以下の点が挙げられます。

顔認識モデルの特性: 使用した 512次元の ArcFace embedding ベクトルが、Voronoi 分割による空間分割に適していたこと。
汎化性能: 数少ないセントロイド（重心）の事前学習データ（JSON/NumPy として保持）が、未知のデータに対しても十分な汎化性能を持っていたこと。

制限事項と今後の展望

一方で、この手法は万能ではありません。特に、テキストと画像のような異なるモダリティを同じ空間にマップする Two-Tower モデル（CLIPなど） の場合、異なるモダリティ間での空間分布の差異により、単純な Voronoi フィルタリングが機能しない可能性があります。Embedding モデルの特性に依存するため、事前の検証が不可欠です。

今後は、テキスト Embedding モデルなど、他のベクトル表現でも同様のアプローチが有効かを検証していく予定です。

内部リリースとフィードバック

今回の実験結果を受けて、約 23,000 枚の画像（約 70,000 の顔データ）を検索できるフロントエンドアプリを Firebase Hosting 上にデプロイしました。現在、PyCon JP 関係者に限定公開し、実際の検索精度や使い勝手についてのフィードバックをもらう予定になっています。