LSH に関するこのペーパーのセクション 5. 、特に生成されたハッシュをバケット化する方法を理解しようとしています。リンクされた論文を引用：
それぞれ d ビットで構成されるビット ベクトルが与えられた場合、N = O(n 1/(1+epsilon) ) のビットのランダム順列を選択します。各ランダム置換 σ に対して、σ によって置換されたビットの辞書式順序で、ビット ベクトルのソートされた順序 O σ を維持します。クエリ ビット ベクトル q が与えられると、次の手順を実行して近似最近傍を見つけます。各順列 σ について、O σ でバイナリ検索を実行して、q に最も近い 2 つのビット ベクトルを見つけます (得られた辞書式順序で)。 σ によって並べ替えられたビットによって)。ここで、q に一致する最長のプレフィックスの長さの順に、バイナリ検索によって返された位置の上下の要素を調べて、ソートされた順序 O σ のそれぞれで検索します。これは、ソートされた順序 O σ ごとに 2 つのポインターを維持することによって実行できます (1 つは上に移動し、もう 1 つは下に移動します)。各ステップで、一致するプレフィックスが最も長い要素に対応するポインターの 1 つを上下に移動します。(ここで、O σ で一致する最長のプレフィックスの長さは、σ によって並べ替えられたビットを使用して q に対して計算されます)。このようにして 2N = O(n 1/(1+epsilon) ) ビットベクトルを調べます。調べたすべてのビット ベクトルの中で、q へのハミング距離が最も小さいものを返します。
私はこのアルゴリズムに混乱しており、その仕組みを理解できていないと思います。
トピックに関するこの質問はすでに見つけましたが、コメントの答えがわかりませんでした。また、ポイント2のこの質問でも同じアルゴリズムが説明されていますが、その仕組みがわかりません。
できるだけシンプルにするために、段階的にどのように機能するかを説明してもらえますか?
わからないことをリストにしてみましたが、実際は下手すぎてほとんどの文章がわかりません！
gsamarasの回答後に編集：
私は答えをほとんど理解しましたが、まだいくつかの疑問があります：
順列をそれぞれソートする必要があるため、
N順列を実行するための総コストはO(Nnlogn)上記の順列 + 並べ替えプロセスは、前処理中に 1 回だけ実行されるか、クエリごとに
q実行されますか? 前処理でもすでにかなりコストがかかるようO(Nnlogn)です。クエリ時にこれを行う必要がある場合、それは惨事です:Dv0とv4を比較する最後のポイントで、qそれらの置換されたバージョンまたは元のバージョン (置換前) を比較します。