asopi tech
asopi techIndie Developer
索引と探す技術（第4回）― 類似の検索と推薦

【2026年10月版】

索引と探す技術（第4回）― 類似の検索と推薦

公開日: 2026/10/02
読了時間: 約 29分

データ

第3回では、語の一致で候補を決めて順位をつける方法を扱った。第4回は、語が異なっていても内容の近いものを探すベクトル検索と推薦を扱う。

1. 一致から類似へ ― 照合の基準と順位の信号

ここまで扱った構造は、二つの層に分けて整理できる。第一の層は候補を決める照合の基準、第二の層は候補に順位をつける信号である。

照合の基準問い構造・手法扱った回
同一性キーが等しいかハッシュ表、B木、ブルームフィルタ第2回
順序・範囲大小で絞れるかソート、B木、疎な主索引第1回、第2回
形文字列や語が出現するか文字列走査、転置索引第3回
距離空間上で近いかベクトル検索第4回
順位をつける信号何を使うか構造・手法扱った回
内容問い合わせと文書の語の一致BM25、リランカー第3回
構造データ同士のリンクPageRank第3回
行動利用者の履歴やクリックランキング学習、協調フィルタリング第3回、第4回

同一性、順序、形では、該当するかどうかが厳密に決まる。距離では近さの程度が連続値で表され、上位 k 件を近似で返す方式が実用の中心になる。厳密な k 近傍を求めることもできるが、高次元で全件との距離を計算すると高価になる。

候補の生成、順位付け、再順位付けという多段の構成は、検索と推薦に共通している。Google の推薦システム入門は、推薦を candidate generation、scoring、re-ranking の三段で説明している。推薦は、利用者の履歴を暗黙のクエリとする検索とみなせる。第一の層の距離で候補を引き、第二の層の行動の信号で並べる。

2. ハッシュの一致による類似検索 ― LSH と MinHash

ハッシュ表はキーが等しいものを同じ位置に集める。書類棚で似た書類を同じ引き出しに入れておけば、引き出しを一つ開けるだけで似た書類がまとめて手に入るように、近いもの同士を同じ位置に集めるハッシュを設計できれば、類似検索をハッシュ表の参照に置き換えられる。これが局所性鋭敏ハッシュ(LSH)である。インディクとモトワニ は1998年に、近いもの同士が衝突する確率が遠いもの同士より十分に高いハッシュ関数を使う方式として LSH を提案した。論文は、前処理が n と d の多項式、クエリ時間が n に対して真に劣線形になることを保証している。n はデータの件数、d はベクトルの次元数で、劣線形とは、データが増えてもクエリにかかる時間がそれより緩やかに伸びることを指す。全件と比べる方法ではデータが倍になれば時間も倍になるので、件数が増えるほどその差は開いていく。

ハッシュの作り方は、類似度の種類ごとに異なる。文書同士の似かたを測るときは、文書を連続する数語ずつの切れ端に分け、二つの文書が共有する切れ端が、どちらかに含まれる切れ端全体の何割にあたるかを似ている度合いとする。この割合がジャッカード係数で、ブローダー の resemblance は、文書を連続する語の列(シングル)の集合とみなしたときのジャッカード係数として定義されている。ブローダーは AltaVista が集めた3,000万を超える文書、150GB を超える入力から、50%の resemblance を基準に360万のクラスタを作った。この推定に使うのが MinHash である。すべての切れ端に同じ規則でくじ番号を振り、各文書で最も小さい番号を持つ切れ端をその文書の代表に選ぶと、二つの文書の代表が一致するのは、両方の切れ端を合わせた中で最小の番号が共有部分に当たったときになる。そのため代表が一致する確率は、共有部分の割合そのものになる。Min-Wise 論文では、この性質が、一様な乱数置換の下で二つの集合の最小要素が一致する確率がジャッカード係数に等しい、と表されている。くじの振り方を変えて代表を何度も選べば、一致した回数の割合から似ている度合いを見積もれる。実際には、各文書に100個の独立な乱数置換それぞれの最小値を保存し、一致した数から resemblance を推定する。

チャリカー はコサイン類似度向けに、ランダムな超平面のどちら側にあるかで1ビットを出すハッシュを示した。空間をでたらめな向きの平面で二つに切ると、向きの近い二つのベクトルは同じ側に入りやすく、間の角度が開くほど平面が二つの間を通りやすくなる。そのため二つのベクトルが同じビットになる確率は 1 − θ/π で、θ はベクトル間の角度である。Datar ら は、ベクトルをでたらめな向きの直線に影として落とし、その直線を一定の幅で区切って同じ区間に落ちたもの同士を同じバケットに入れる方式で、ユークリッド距離向けのハッシュを作った。影の作り方に p-安定分布という性質を持つ乱数を使うと、影同士の距離に元の距離が反映される。論文はこの方式について、合成データの実験で kd木より最大40倍速かったと報告している。

ベクトルを短い符号に置き換える別の方法に、直積量子化がある。長いベクトルをいくつかの区間に切り、区間ごとに代表点の一覧を用意しておき、各区間で最も近い代表点の番号だけを記録する。住所を都道府県、市区町村、町名と区切って、それぞれを一覧の中の番号で書くのに近い。Jégou ら は、空間を低次元の部分空間の直積に分け、部分空間ごとに量子化して、ベクトルを各部分空間の量子化番号からなる短い符号で表す方式として、これを定式化した。128次元の SIFT を64ビットで表す設定では、8つの部分空間にそれぞれ256個の重心を持たせ、符号は8バイトになる。区間ごとの番号の組み合わせで点を表すので、表せる点の数は256を8回掛けた数になり、少ない記録で細かく区別できる。128次元の float32 は512バイトなので、64分の1に縮む。

大規模なベクトル検索では、ベクトルの分布を利用する手法が LSH より優位にある。Jégou らは同じ論文で、実データでは LSH がそうした手法に劣ると書いている。ANN-Benchmarks も、多くのデータセットでグラフ型が最良で、HNSW がしばしば最速だと報告している。LSH の利点は、類似度の検索をハッシュ表と同じ等価判定の道具で扱える点にある。そのため集合の重複検出のように、ベクトルの距離以外の類似度を扱う場面で役に立つ。

3. ベクトル検索 ― 近似と引き換えの速度

従来の検索が値の大小、等価性、語の一致を使ってきたのに対し、ベクトル検索は文書・画像・音声を高次元ベクトルへ変換し、距離や内積が近い対象を探す。高次元空間で全ベクトルとの距離を計算すると高価になるため、多くのシステムは近似最近傍探索(Approximate Nearest Neighbor、ANN)を使う。

方式基本発想
Flat全件との距離を計算する
IVF空間をクラスタへ分割し、近いクラスタだけ調べる
PQベクトルを部分空間に分けて量子化する
HNSW階層的な近傍グラフをたどる
DiskANNSSD 上の近傍グラフを効率的に探索する

2016年に提案された HNSW は、疎な上位層のグラフから探索を始め、より密な下位層へ降りながら近傍を探すグラフ型索引である。遠くの目的地へ行くときに、まず高速道路で近くまで行き、一般道、さらに細い道へと降りていくのと同じで、上位層では少ない点を大きな歩幅で渡り、下位層で細かく近傍を探す。DiskANN は、巨大なベクトル集合を SSD とメモリに分けて置き、十億規模の近傍検索を行うために設計された。NeurIPS 2019 の論文では、64GB の RAM と安価な SSD を積んだ一台のワークステーションで十億点規模を扱っている。

pgvector は HNSW と IVFFlat を提供している。HNSW は速度と再現率の兼ね合いで優れる一方、構築が遅く、メモリも多く消費する。IVFFlat のほうは、事前の学習とクラスタ分割が要る。

近似である以上、正しい近傍の一部を見逃しうる。そのため評価指標も変わり、Recall@k、Precision@k、nDCG、MRR といった精度の指標に加えて、索引の構築時間、更新の遅延、クエリ遅延の p95 と p99 を見る。ANN での Recall@k は、全件を調べて求めた本当の近傍 k 件のうち、近似検索が返した k 件に入っていた割合で、見逃しの少なさを表す。p95 と p99 は、100回のクエリを速い順に並べたときの95番目と99番目の遅延にあたり、平均では埋もれる遅いクエリの待ち時間を表す。ベクトルあたりのメモリ、鮮度(freshness)、フィルタ付き検索での再現率も同時に効いてくる。

平均値だけを見ると失敗が隠れる。2026年の研究は、Recall@k の平均が同じ二つのシステムでも、個々のクエリでは大きく異なる挙動を示すことを指摘した。一方はどのクエリでもほどほどの再現率を出し、もう一方は大半のクエリで満点に近いかわりに一部のクエリでほとんど近傍を拾えない、という違いが平均では同じ値に見えてしまう。難しいクエリの長い裾が平均に埋もれるため、論文は、クエリごとの再現率に合格ラインを決め、それを満たすクエリが全体の何割あるかを数える指標を提案した。これが、閾値 δ を超えるクエリの割合として定義される Robustness-δ@K である。ANN の結果を正解として扱っていると、索引の構築条件や検索パラメータを変えた時点で結果が変わることを見落とす。

4. 更新され続けるベクトル索引

近年の提案の多くは、一度構築した索引を更新やアクセスの変化に合わせて調整していく適応型の設計をとる。論点はインプレース更新、トゥームストーン処理、部分的な再構築、ストリーミング挿入などで、時間経過による分布の変化、偏り(skew)のあるアクセスへの適応、メモリとディスクの階層化も同じ文脈で扱われる。

FreshDiskANN は、十億点規模のグラフ索引で毎秒数千件の挿入・削除・検索を並行して処理しながら、本当の近傍5件のうち返した5件に入る割合である 5-recall@5 で95%以上を保つ。鮮度を保つためのコストは、既存手法の5分の1から10分の1に下がったと報告している。OSDI 2025 で発表された Quake は、多階層のパーティションを更新とアクセスパターンに応じて調整する。パーティションのサイズとアクセス頻度から遅延を予測するコストモデルを持ち、検索パラメータも動的に設定する。LSM-VEC は HNSW 型の近傍グラフを分割し、上位層をメモリに、最下層を LSM-tree に置いて、更新を元の位置で書き換えずに処理する。古典的な LSM-tree が、ここで最新のベクトル検索と再び結びつく。

量子化と低精度化も進んでいる。ベクトルを float32 から int8 や二値、直積量子化へ変換すると、メモリとキャッシュの使用量と距離計算の負荷がまとめて減る。低精度のベクトルで候補を生成し、少数の候補だけを元のベクトルで再ランキングする構成が広く使われている。

5. 索引データと分布の異なるクエリ

ベクトル索引の性能は、索引したデータの分布とクエリの分布の関係に左右される。OOD-DiskANN の論文は、HNSW、FAISS-IVF、DiskANN のようにデータに依存する索引が、クエリが索引と別の分布にあると優位を失うと指摘した。画像の索引にテキストのクエリを投げる例では、固定の再現率を目標にしたとき、分布外のクエリの遅延が分布内より一桁以上悪化する。

big-ann-benchmarks の NeurIPS 2021 の競技では、同じベースラインでも、データセットによって再現率が大きく違った。10000 QPS で BIGANN は 0.6345、Text-to-Image は 0.0693 である。論文は、Text-to-Image ではクエリとベースの分布がまったく異なり(テキストの埋め込みと画像の埋め込み)、量子化や圧縮を使う手法には特に難しいと説明している。

クエリごとの難しさにも差がある。Aumüller と Ceccarello の研究は、クエリごとの局所内在次元(LID)が高いほど再現率が下がることを示した。ベクトルが何百次元あっても、あるクエリの周りでデータが実際に広がっている方向の数は少ないことがあり、局所内在次元はこの周辺での広がりの次元数を、クエリからの距離を少し広げたときに近傍の件数がどれだけ急に増えるかで見積もった値である。値が高いクエリの周りでは、近い点と少し遠い点の距離の差が小さくなり、近いものを選び分けるのが難しくなる。どの実装もクエリの難しさに適応できないため、平均の再現率を高く保つには難しいクエリに合わせたパラメータが必要になり、その分だけ易しいクエリが大きく遅くなる。

分布外に特化した手法を選ぶべきかどうかも、データによって変わる。VIBE は22の実装を、分布内の11と分布外の8のデータセットで比較した。テキスト検索や text-to-image の分布外データでは、汎用の最良の手法が分布外特化の手法を上回った。一方、近似アテンションの計算に使う内積検索のデータはクエリと文書の分布の差が最も大きく、Glass と hnswlib は評価したすべての設定で平均再現率が50%に届かなかった。分布外特化の RoarGraph は、あるデータでは Glass を上回り、別のデータでは下回る。どの手法がよいかは、最後は自分のクエリで測って判断するしかない。

6. 推薦 ― 履歴を暗黙のクエリとする検索

利用者の履歴から好みそうな項目を薦める推薦も、候補を引いて並べる構造をとる。YouTube の2016年の論文は、膨大な動画から候補を絞る候補生成の段と、別のランキングモデルで順位をつける段の二段で推薦を構成している。

候補生成の中心は、利用者と項目を同じ空間のベクトルにして、近いものを引く処理である。行列分解は、利用者ごとに好みの傾向を表す数値の並びを、項目ごとにその項目の性質を表す数値の並びを学習し、両者の内積で好みを表す。アクション映画を好む向きを持つ利用者と、アクションの要素が強い向きを持つ映画であれば、内積が大きくなってその映画が薦められる。近さを内積で測るので、候補の検索は最大内積探索(MIPS)になる。距離であれば、A が B に近く B が C に近いとき A と C もある程度近いという性質(三角不等式)が成り立ち、近傍探索の多くはこれを手がかりに探す範囲を絞る。内積では、長いベクトルはどの向きのクエリに対しても値が大きくなりやすく、この手がかりが崩れる。Shrivastava と Li は、内積が三角不等式を満たさないため、距離の近傍探索に使う既存の LSH の枠組みが MIPS には不十分であることを示し、非対称なハッシュへ拡張した。評価には Netflix と MovieLens の項目推薦を使っている。

推薦の手法の優劣も、データと評価方法によって変わる。Ferrari Dacrema らの再現研究は、トップレベルの会議で発表された18のニューラル推薦手法のうち、合理的な労力で再現できたのは7つだけで、その7つのうち6つは近傍法やグラフに基づく比較的単純な手法にしばしば負けると報告した。Rendle らの再評価では、ハイパーパラメータを適切に選べば、単純な内積が学習された類似度(MLP)を大きく上回った。内積であれば、検索の面でも効率のよい手法を使える。

7. 語彙検索とベクトル検索の統合パイプライン

ベクトル検索は意味的な類似性を扱えるが、固有名詞、製品番号、エラーコード、日付、正確な引用では今も語彙検索のほうが強い。識別子や否定表現、完全一致を求める問い合わせを意味検索だけに任せると、近いが別のものが上位に来る。

語彙検索が強い場面は、実測にもはっきり表れている。LIMIT は、単一ベクトルの埋め込みが返せる上位 k の部分集合の数は埋め込みの次元に縛られるという理論をもとに、単純なクエリからなる合成データセットを作った。このデータでは最先端の埋め込みが失敗し、BM25 はほぼ満点だった。ただし言い換えた版では BM25 の成績が約90%落ち、多くの単一ベクトルのモデルを下回る。論文自身も、語彙のモデルにも弱点があると書いている。BRIGHT は推論を要する問いを集めた検索ベンチマークで、MTEB の検索タスクで nDCG@10 が 59.0 だったモデルが、BRIGHT では 18.3 に下がった。BM25 の12データセット平均は 14.5 である。

そのため実用の検索では多段の構成がとられる。フィルタで対象集合を限定し、BM25 で語彙の候補を、ベクトル ANN で意味の候補をそれぞれ生成する。両方の順位を統合してからクロスエンコーダや LLM で再ランキングし、最後に権限、鮮度、業務ルールを適用する。Elastic は、BM25 などの語彙検索と意味的なベクトル検索を一つの順位へ統合する方式をハイブリッド検索として説明している。

順位の統合には、加重スコア和、スコアの正規化、Reciprocal Rank Fusion が使われ、学習済みのランキングモデルやリランカーを挟む構成もある。語彙検索とベクトル検索ではスコアの分布も値域も違う。そのため、正規化か順位に基づく統合を挟んで、片方のスコアが順位を支配するのを防いでいる。Reciprocal Rank Fusion は順位に基づく統合の代表で、各検索での順位に定数を足したものの逆数を点数とし、それを足し合わせて並べ直す。スコアの値を捨てて順位だけを見るので、物差しの違う二つの検索結果を同じ重さで混ぜられ、どちらの検索でも上位に来た文書が最終的な上位に残る。

候補生成器と判定器を何段つなぐか、各段で何件残すか、統合をスコアと順位のどちらで行うか。これらが、検索システムの設計の中心にある項目だ。

第5回では、カーナビの経路や将棋の次の一手のように、候補の全体を見渡せない問題の探索を扱う。

参考リンク