余弦類似度LSHとランダム超平面

Question

ランダムな超平面を使って高次元で最近傍探索に関するいくつかの解法を読みましたが、バケットの仕組みについてはまだ混乱しています。私は100次元のベクトルと100万のクエリの形で100万の文書を持っています。各クエリについて、コサイン類似度に基づいて最も近い隣を見つける必要があります。ブルートフォースのアプローチは、クエリのcosineの値をすべて1億のドキュメントで見つけ、値が1に近いものを選択することです。ドキュメントをバケットに入れて、私がそうでないようにランダムなハイパープレーンのコンセプトに苦しんでいますクエリごとにcosine値を100万回計算する必要があります。

Answer 1

幾何学的に考える。高い次元の空間でポイントのようなデータを想像してみてください。

ランダムな超平面（高次元の平面のみ）を作成し、想像力を使って縮小します。

いくつかの点が他から離れて（そのパーティション内のすべての点を、粗い近似であろう）に配置されているパーティションを作成するこれらの超平面カットデータ（点）、、。

ここで、バケットは、超平面によって形成された区画に従って配置される必要があります。その結果、すべてのバケットにはポイントセットの合計サイズよりもはるかに少ないポイントが含まれます（これまで説明したすべてのパーティションには、ポイントセットの合計サイズよりも少ないポイントが含まれているためです）。

結果として、クエリをポーズすると、（バケットの助けを借りて）合計サイズよりもずっと少ないポイントがチェックされます。それはすべての点をチェックするブルートフォースアプローチよりもはるかに優れています（より速く）ことを意味します。