概要

近似最近傍探索とメタデータフィルタリングについて調べたことをサクッとまとめます。
今回は 2 種類の愚直なアプローチとその問題点について書きます (というかここで力尽きた)。

モチベーション

ベクトル検索が流行っている今日この頃、近似最近傍探索もよく使われてますよね。もちろん私のお勤め先でも使われております。
最近は近似最近傍探索とメタデータフィルタリングを組み合わせたデータベース※なんかもあるみたいです。すげぇ〜。
そこで気になったんですが、近似最近傍探索とメタデータフィルタリングってどうやって組み合わせてるんでしょうか？
「近似最近傍探索してから後処理でフィルタリング」でとりあえず要件を満たせそうですが、なんか効率悪いだろうなあ、なんかいい方法があるんだろうなぁ、と思っている感じです。
※ Pinecone, qdrant, Vertex AI Vector Search etc.

前提

近似最近傍探索

ある商品に意味的に類似する商品を大量の候補の中から高速に見つける、みたいなことができます。

(僕) この商品に似た商品はどれ？
(近似最近傍探索ｸﾝ) これだよ！

他にも Two tower model なんかと組み合わせてユーザーと相性の良い商品を高速に見つける、みたいなこともできます。便利だなぁ。

近似最近傍探索 × メタデータフィルタリング

ある商品に意味的に類似する商品を、大量の候補の中からカテゴリを絞り込みつつ高速に見つける、みたいなことができます。

(僕) この商品に似たシャツはどれ？
(近似最近傍探索ｸﾝ) これだよ！

便利そうです。
それに実サービスでは割とありがちな要求なんじゃないでしょうか？

愚直なアプローチその課題

前処理でフィルタリング

近似最近傍探索の前にフィルタリングすることで要件を満たせそうですが、実は問題があります。
近似最近傍探索の前にフィルタリングする場合、フィルタリング結果ごとに近似最近傍探索のインデックスを用意してあげる必要があるのです。めんどくさそうですね。
例えば 10 種類の商品カテゴリと 10 種類の色の組み合わせで商品をフィルタリングする場合どうなるでしょうか？インデックスが 100 個も必要です。やっぱりめんどくさそうですね。
商品の価格帯をフィルタリングの条件に追加したい、ですって？もう無理ですね。

なおフィルタリングの種類が数個だけで増えることもないのであれば、この方法もアリかもしれません。
またフィルタリング後のアイテム数がかなり少なくなることが保証されているような場合には、ブルートフォースで近傍探索しちゃってもいいのかもしれませんね。であればインデックスたくさん運用しなきゃ行けない問題は発生しなさそうです。

後処理でフィルタリング

近似最近某探索の後にフィルタリングすることで要件を満たせそうですが、こちらも問題があります。
例えばある T シャツに似た雰囲気のシャツを 10 個取得したいとします。
フィルタリングでいくつか除外されることを見越して 20 個の類似商品を ANNS で取得し、その後シャツのみに絞り込むとしましょう。
残念ながら ANNS で取得した 20 個のうちシャツは 5 個だけでした。10 個欲しかったのに残念です。最初に取ってくる商品数が 20 個じゃ少なかったみたいです。
今度は ANNS で取得する商品を 100 個にしてみました。するとフィルタリング後に 10 個以上の商品が残りました。やったね。
でもこれもダメですよね。だって無駄な計算がたくさん必要になりますから。

さいごに

前処理でのフィルタリング、後処理でのフィルタリングには問題があることがわかりました。
次回以降は上記の問題を解決する方法について調べてまとめてみようと思います。
Pinecone さんや qdrant さんのブログが参考になりそうかなあ、と思っています。

参考文献

(順不同)

pinecone さんのブログ: https://www.pinecone.io/learn/vector-search-filtering/
qdrant さんのブログ: https://qdrant.tech/benchmarks/