哪个minhash比simhash更有优势？

Question

我正在使用simhash，但也看到minhash更有效。

但我不明白。

请给我解释一下: minhash比simhash更有优势的是什么？

Answer 1

Simhash比minhash更快，并且通常比minhash对内存的要求更小，但它的局限性在于它只能检测非常相似的地方。如果两个项目的差异超过很小的量，则不会检测到它们的相似性。另一方面，Minhash可以用来检测甚至相当远的相似性，比如彼此之间只有5%的相似性。Simhash的理解也稍微复杂一些。

Minhash依赖于为每个项目生成多个哈希，例如通常在20到400个64位哈希之间。这些散列都需要存储，以及它们所属的项的ID，并通过散列进行索引。要查找与给定项目具有50%估计相似度的所有项目，您必须找到共享至少50%的给定项目散列的所有其他项目。这可能涉及枚举相当大数量的hash-itemID对。

另一方面，Simhash仅对每个项目使用单个散列，例如64位散列；并且该散列的生成使得非常相似的项将具有非常相似的位模式的散列。该散列必须存储在多个表(例如，8个不同的表)中(连同项的ID)，每个表以不同的方式排列散列的位，并且每个表以数字顺序对排列后的散列进行排序。使用多个表可以实现一个聪明的技巧，即您可以快速找到与给定散列相差最多k位的所有散列；问题是k不能很大:根据您希望存储的项的数量，整个散列中有多少位，以及您可以在内存中保留多少个表，k可能低至3，也可能高达6或7。请参阅此explanation of simhash。

Minhash和simhash的速度都依赖于将它们的表保存在主内存中，尽管如果您需要克服内存限制，它们都可以被拆分到多台机器上。创建simhash的方法被谷歌拥有的一项专利所涵盖，尽管他们似乎至少允许将该算法用于非商业用途。

Answer 2

在simhash中，我们不需要存储超平面。它有稍微差一点的误差界。Simhash lecture