問題タブ [minhash]

C++11 で一部の文字列要素の類似検索に minhash と LSH を実装しています。私の実装の minhash スケッチは、200 個の 64 ビット整数のベクトルですvector<uint64_t> MinHashSketch。200 万を超えるエントリがあり、スケッチ生成部分にはそれほど時間がかかりません。ただし、バケット化段階には時間がかかります。もう少し速くするための提案を得ることができるかどうか疑問に思っています。以下は、LSH を使用したバケット ステージです。

スケッチ内の連続した要素を取得して、バケット ID になるハッシュを作成しています。の場合bsize = 5、(i 番目の要素の) の要素がバケット ID を形成します1-5, 6-10, 11-15, ... 196-200。MinHashSketch[i]それを行うコードに従ってください。

私が理解している限り、LSH メソッドの主な機能の 1 つは、基礎となるハッシュ (多くの場合、ミンハッシュ) を超えたデータ削減です。R でパッケージを使用してきtextreuseましたが、生成されるデータのサイズに驚いています。textreuseは査読済みのROpenSciパッケージなので、正しく機能すると思いますが、私の疑問は解決しません。

ミンハッシュ関数と LSH 関数にそれぞれ 256 個の順列と 64 個のバンドを使用するとします。これは、50% という低い類似性を相対的な確実性(~98%) で検出するためによく使用される現実的な値です。

(256 perms)を使用してランダムなテキスト ファイルをハッシュし、TextReuseTextDocumentそれを に割り当てるとtrtd、次のようになります。

次に、このオブジェクト (64 バンド) の LSH バケットを作成し、に割り当てますl。次のようになります。

そのため、LSH バケットに保持されているハッシュは、元のミンハッシュよりも 6 倍大きくなります。textreuse これは、md5 ダイジェストを使用してバケット ハッシュを作成するために発生することを理解しています。

しかし、これはあまりにも無駄/やり過ぎではなく、改善できないのでしょうか? 私たちのデータ削減技術がここまで膨れ上がってしまうのは普通のことでしょうか? また、元のハッシュ (perms = 256 および band = 256 と同様) に基づいてドキュメントを照合し、しきい値を使用して誤検知を除外する方が効果的ではないでしょうか?

Mining of Massive Datasetsなどの典型的なテキストを確認しましたが、この特定の実装については疑問が残ります。また、この質問は好奇心からだけでなく、必要性からでもあることに注意してください。数百万または数十億のハッシュがある場合、これらの違いは重要になります。