1

ドキュメントを含む大規模なpostgresqlデータベースがあります。テーブル内の行として表されるすべてのドキュメント。新しいドキュメントがデータベースに追加されたら、重複をチェックする必要があります。selectしかし、完全に一致するものを見つけるためだけに使用することはできません。2つのドキュメントはわずかに異なる場合がありますが、それでも重複と見なすことができます。たとえば、一部のマイナーフィールドが異なり、他のすべてのフィールドが等しい場合などです。

私はこの問題を研究し、この問題を解決する方法を見つけます。すべてのドキュメントの署名を計算MinHashし、転置インデックスを作成して、データベースから同様のドキュメントをクエリすることができます。MinHashしかし、リレーショナルデータベースにマッピングする方法がわかりません。

私が理解しているように、MinHash署名はN個のハッシュのリストです。ここでNはいくつかの属性です。類似性は次のように計算されます。

# Given 2 signatures Sa and Sb containing N hashes.
# Calculate number of equal hashes Neq.
number_of_equal_hashes = 0
for ix in range(0, N):
    if Sa[ix] == Sb[ix]:
        number_of_equal_hashes += 1
similarity = float(number_of_equal_hashes)/N

すでに2つの署名がある場合、これは簡単です。問題は、データベース内で類似性がある程度の値以下のすべてのドキュメント（対応する署名を含む）を見つけることです。

たとえば、次のように複数の列を持つテーブルを作成できます。

| minhash0 | minhash1 | minhash3 | docid |

各minhashX列は、ドキュメントの属性の1つのminhashに対応しdocid、ドキュメントの識別子です。次の方法で同様のレコードをクエリできます。

select * from invidx
where ((case when minhash0=minhash2search0 then 1 else 0 end) +
       (case when minhash1=minhash2search1 then 1 else 0 end) +
       (case when minhash2=minhash2search2 then 1 else 0 end))/N > THRESHOLD

ここで、minhash2searchXは新しいドキュメントのミンハッシュであり、THRESHOLDは最小限の類似性です。ただし、このアプローチではフルスキャンが必要です。このアルゴリズムを高速化する方法はありますか？

4

2 に答える 2

2

転置インデックスの使用上の利点を使用するには、目的に合わせて全文検索エンジンを使用することをお勧めします。たとえば、LuceneまたはSolr（Luceneに基づく）

ドキュメント（dbレコード）のMinHashesに関連付けられたフィールドを含む「ドキュメント」（Luceneの観点から）を作成できます。数値フィールドにもインデックスを付けることができることに注意してください（スキームでフィールドタイプを記述する必要があるだけです）。また、データベースのレコードにLuceneの「ドキュメント」をマッピングするには、各ドキュメントの主キーを保存する必要があります。

ドキュメントのコレクション全体にインデックスを付けます。

特定のドキュメントに類似したドキュメントを見つけるには、各フィールドのMinHashesを計算し、Luceneに類似のドキュメントを照会する必要があります。

field1:MinHash1 OR field2:MinHash2 OR ...

より多くのフィールドがドキュメントに一致すると、ランクが高くなります。したがって、最高ランクのドキュメントをいくつか取得して、決定を下すことができます-あなたのケースでそれらが本当に類似しているかどうか

また、フィールドのブーストはあなたにとって役立つかもしれません

于 2012-12-05T12:43:05.140 に答える
1

ハッシュテーブルには次の2つの列が含まれている必要があります。

| minhash | docid |

minhashでインデックスを作成する必要があります。

新しいドキュメントが到着したら、その各ミンハッシュを順番に検索し、テーブルにクエリを実行して、そのミンハッシュを共有している以前のドキュメントを見つけます。これらの以前のドキュメントで共有されているミンハッシュの数の集計を作成し、共有されているミンハッシュの50％未満（たとえば）のミンハッシュをすべて破棄します。これにより、少なくとも（推定）50％類似しているすべてのドキュメントのセットが効率的に生成されます。

最後に、新しいドキュメントのミンハッシュごとに新しい行を挿入します。

LuceneまたはSolrを使用することは悪い解決策です。より多くのストレージが必要になり、実装がより複雑になり、効率が大幅に低下します。はい、Luceneにminhashesのインデックスを作成させ、stemmが示唆するようにクエリを実行することができます。これにより、データサイズに応じて、1つのミンハッシュ（数万または数十万）を共有するすべてのドキュメントが返されます。次に、「類似性」機能を使用して、これらのそれぞれを受信ドキュメントと個別に比較する必要があります。これは非常に低速です。

Luceneは、特定のキーワードを共有するドキュメントを検索するための「MoreLikeThis」機能を提供しますが、これは、minhashアプローチが検索する多くの同様のドキュメントを見逃します。

于 2019-02-13T02:34:49.333 に答える