data-mining - locality-sensitive ハッシュで「locality-sensitive」とは何を表していますか?

Question

とはどういう locality-sensitive意味locality-sensitive hashingですか? この用語の正式な定義はありますか?

Answer 1

通常、衝突のリスクを軽減するために、近くの値を分離するためにハッシュ関数が使用されます。暗号化ハッシュについて考えてみてください。文字を変更するたびに、ハッシュ コードを完全に変更する必要があります。

これは、LSH で使用されるハッシュ関数には当てはまりません。技術的には、ハッシュ関数には当てはまりますが、ハッシュの直前のステップには当てはまりません。データはバケットに入れられます。これは損失の多い操作であり、通常、近くのポイントが同じバケットに入れられます。その後、バケット番号のみが実際にハッシュ化 (IIRC) されるため、何百万ものバケットは取得されず、必要な数だけ取得されます。

マッピングとビニングに使用する独立した関数がある場合、それらは重複する可能性が高いため、クエリ ポイントが含まれるハッシュ衝突バケットの少なくとも 1 つですべての真の近傍を見つけることができます。