simhashよりもさらに有利なミニハッシュはありますか？

Question

私はsimhashと一緒に働いていますが、minhashがより効果的であることも見ています。
しかし、私は理解していません。
私のために説明してください：simhashよりもさらに有利なミニハッシュはありますか？

Answer 1

simhashでは、超平面を保存する必要はありません。エラー範囲が少し悪化しています。 Simhash lecture

Answer 2

Simhashは高速であり、通常はminhashよりもメモリ要件が小さいですが、非常に近い類似点しか検出できないという事実によって制限されています。 2つの項目が少々異なる場合、それらの類似性は検出されません。一方、Minhashは、5％の類似度しか持たない項目など、非常に遠い類似点を検出するためにも使用できます。 Simhashはまた、理解するのが少し複雑です。

Minhashはアイテムごとに複数のハッシュを生成することに依存しています。通常は20〜400の64ビットハッシュの間にあります。これらのハッシュはすべて、ハッシュで索引付けされたアイテムのIDとともに格納する必要があります。たとえば、すべての商品を見つけるには特定のアイテムとの推定類似度が50％であれば、そのアイテムのハッシュの少なくとも50％を共有する他のすべてのアイテムを見つける必要があります。これには、かなり多数のハッシュ-IDIDペアを列挙することが含まれます。一方、Simhashはアイテムごとに1つのハッシュしか使用しません。 64ビットのハッシュ。このハッシュは、非常に類似したアイテムが非常に類似したビットパターンを有するハッシュを有するように生成される。このハッシュは、複数のテーブル（例えば8つの異なるテーブル）に格納され、各テーブルは異なる方法でハッシュのビットを置換し、各テーブルは置換されたハッシュを数値順にソートする必要があります。複数のテーブルを使用すると、指定されたハッシュから最大でnビットだけ異なるすべてのハッシュをすばやく見つけることができます。問題は、nは大きくできません。格納するアイテムの数、ハッシュ全体のビット数、メモリに保持できるテーブルの数によっては、nは3または可能であれば6または7になります。

Minhashとsimhashは、メモリの制約を克服する必要がある場合、両方のマシンで分割することができますが、どちらもテーブルをメインメモリに保持することによって速度が異なります。 simhashを作成する方法は、Googleが保有する特許によって保護されていますが、アルゴリズムの非商用利用を許可するようです。