什麼比simhash更有利於minhash？

Question

我正在使用simhash，但也看到minhash更有效。
但我不明白。
請爲我解釋：什麼比simhash更有利的minhash？

Answer 1

在simhash中，我們不需要存儲超平面。它有更差的誤差界限。 Simhash lecture

Answer 2

Simhash速度更快，通常內存要求比minhash要小，但它受限於它只能檢測非常接近的相似性。如果兩個項目的差異不是很小，它們的相似性將不會被檢測到。另一方面，Minhash可以用來檢測相當遠的相似性，例如相互之間只有5％相似度的項目。 Simhash也有點複雜的理解。

Minhash依靠每個項目產生多個哈希值，例如，通常介於20和400之間的64位散列。這些散列都需要存儲，以及它們所屬的項目的ID，通過散列索引。要查找所有包含例如估計與給定項目的相似度爲50％，則必須找到至少共享給定項目哈希值的50％的所有其他項目。這可能涉及枚舉相當大數量的hash-itemID對。另一方面，Simhash只對每個項目使用單個散列，例如，一個64位散列;並生成這個散列，使得非常相似的項目將具有非常相似的位模式的散列。該散列必須與多個表（例如8個不同的表）一起存儲（與該項的ID一起），每個表以不同的方式排列散列的位，並且每個表按數字順序排列排列的散列。使用多個表可以實現一個聰明的技巧，通過這個技巧，您可以快速找到所有散列，它們與給定的散列最多相差n位;問題是n不能很大：取決於你期望存儲多少項目，整個散列中有多少位，以及你可以保留在內存中的表數量，n可能低至3或可能高達6或7.

Minhash和simhash都依賴於它們將表保存在主內存中的速度，儘管如果需要克服內存限制，它們都能夠在多個機器上分割。創建simhash的方法由Google持有的專利所涵蓋，儘管他們似乎允許至少非商業用途的算法。