data-mining - `locality-sensitive` 在局部敏感散列中代表什么？

Question

locality-sensitive代表什么 locality-sensitive hashing？这个词有正式的定义吗？

Answer 1

LSH 将高维向量映射到桶，并尝试确保彼此“接近”的向量映射到同一个桶。“近”的定义只是关于某个距离函数（例如欧几里得）的邻域。

“局部”是指空间上的区域；“敏感”意味着附近的位置映射到同一个桶。换句话说，散列函数的输出依赖于（敏感于）空间中的位置（局部性）。

这是我的理解。我相信理论上的人必须有更正式的定义。希望这可以帮助。

Answer 2

通常，散列函数将用于分隔附近的值，以减少冲突的风险。想想密码散列：你确实希望每一个字符的改变都能完全改变散列码。

这不适用于 LSH 中使用的散列函数。好吧，从技术上讲，它适用于散列函数，但不适用于散列之前的步骤：将数据放入桶中，这是一种有损操作，通常会将附近的点放入同一个桶中。之后，实际上只有存储桶编号被散列（IIRC），因此您不会获得数百万个存储桶，而只会获得所需数量的存储桶。

如果您有用于映射和分箱的独立函数，它们可能会重叠，以便您可以在查询点所在的至少一个哈希冲突桶中找到所有真正的邻居。