如何在位置敏感哈希(LSH)中将签名矩阵哈希到桶



我了解通过应用哈希函数从瓦片创建签名矩阵背后的算法。然而,我不明白如何将签名矩阵中的特定带散列到桶中。假设在矩阵M的频带b1中,我们对文档C1-C5具有以下值:

C1  C2  C3  C4  C5
1   0   0   0   2
3   2   1   2   2
0   1   3   1   1

通过查看这些值,我们可以看到C2和C4在这个带中是相同的,它们应该散列到同一个桶中。但其他列将散列到不同的桶中。

我的问题是如何将这些列散列到桶中,并在不进行实际比较的情况下知道它们是否相同。我应该如何定义散列函数来将列映射到bucket?比如列中元素的总和?

简单的方法,假设您有1024个桶

hash = 1 
for val  in column:
hash = (( hash * 33 )  +  val ) % 1024

% 1024必然是您拥有的存储桶数。33是一个神奇的数字,在实际应用中能很好地与字符串配合使用

数字33的神奇之处(为什么它比许多其他常数更好用,无论是否素数(从未得到充分解释。

请参阅http://www.cse.yorku.ca/~oz/hash.html

最新更新