局部敏感哈希值是什麼意思？

Question

locality-sensitive代表locality-sensitive hashing是什麼意思？這個術語是否有正式的定義？

Answer 1

LSH將高維矢量映射到桶，並試圖確保彼此「靠近」的矢量映射到同一個桶。 「近」的定義就是關於某個距離函數（如歐幾里得）的鄰域。

「地點」是指空間區域;和「敏感」意味着附近的位置被映射到相同的桶。換句話說，哈希函數的輸出取決於（對於空間位置（當地）的位置）。

這是我的理解。我相信理論家們必須有更正式的定義。希望這可以幫助。

Answer 2

通常，散列函數將被用於單獨的附近的值，以降低碰撞風險。想想密碼哈希：你確實希望每一個單獨的字符改變都能完全改變哈希碼。

這不適用於在LSH中使用的散列函數。從技術上講，它適用於散列函數，但不適用於散列之前的步驟：將數據放入存儲區中，這是一種有損操作，通常會將附近的點放入同一個存儲區。之後，只有桶號實際上被散列（IIRC），所以你不會得到數百萬桶，但只有期望的數量。

如果您有使用映射和分級獨立的功能，他們可能會重疊，因此，你可以找到在哈希衝突桶查詢點是在至少一個所有真正的鄰居。