1

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

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

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

object.size(trtd$minhashes)
> 1072 bytes

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

object.size(l$buckets)
> 6704 bytes

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

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

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

4

1 に答える 1

1

パッケージ作成者はこちら。はい、必要以上のハッシュ/バンドを使用するのは無駄です。(ただし、ここではキロバイトについて話しているため、元のドキュメントよりもはるかに小さい可能性があることに注意してください。)

問題は、何が必要かということです。同一に近い (つまり、Jaccard スコアが 1.0 に近い) 一致のみを検索する必要がある場合は、特に機密性の高い検索は必要ありません。ただし、部分的な重複 (つまり、0 に近い Jaccard スコア) のみを共有する潜在的な一致を確実に検出する必要がある場合は、より多くのハッシュ/バンドが必要です。

MMD を読んだことがあるから、そこで方程式を調べることができます。ただし、パッケージには 2 つの関数があり、ドキュメントはこちらで、必要なハッシュ/バンドの数を計算するのに役立ちます。lsh_threshold()検出される Jaccard スコアのしきい値を計算します。whilelsh_probability()は、特定の Jaccard スコアを持つドキュメントのペアが検出される可能性を示します。検索の問題に最適なハッシュ/バンドの数が得られるまで、これら 2 つの関数を試してみてください。

于 2020-08-16T20:24:32.633 に答える