Set Digest関数

Trinoには、MinHash技術を扱ういくつかの関数が用意されています。

MinHashは、2つのセット間のJaccard類似度係数を迅速に推定するために使用されます。

これは、データマイニングで広範囲に重複するウェブページを検出するために一般的に使用されます。この情報を使用することで、検索エンジンは効率的に、検索結果にほぼ同一の2つのページが表示されないように避けることができます。

次の例は、セットダイジェスト関数を使用してテキスト間の類似性を単純に推定する方法を示しています。入力テキストは、4文字のシングルに分割され、これらがそれぞれの初期テキストのセットダイジェストの入力として使用されます。セットダイジェストは、それぞれの初期テキストの類似性を近似するために比較されます：

WITH text_input(id, text) AS (
VALUES
(1, 'The quick brown fox jumps over the lazy dog'),
(2, 'The quick and the lazy'),
(3, 'The quick brown fox jumps over the dog')
),
text_ngrams(id, ngrams) AS (
SELECT id,
transform(
ngrams(
split(text, ' '),
4
),
token -> array_join(token, ' ')
)
FROM text_input
),
minhash_digest(id, digest) AS (
SELECT id,
(SELECT make_set_digest(v) FROM unnest(ngrams) u(v))
FROM text_ngrams
),
setdigest_side_by_side(id1, digest1, id2, digest2) AS (
SELECT [m1.id](<http://m1.id/>) as id1,
m1.digest as digest1,
[m2.id](<http://m2.id/>) as id2,
m2.digest as digest2
FROM (SELECT id, digest FROM minhash_digest) m1
JOIN (SELECT id, digest FROM minhash_digest) m2
ON [m1.id](<http://m1.id/>) != [m2.id](<http://m2.id/>) AND [m1.id](<http://m1.id/>) < [m2.id](<http://m2.id/>)
)
SELECT id1,
id2,
intersection_cardinality(digest1, digest2) AS intersection_cardinality,
jaccard_index(digest1, digest2)            AS jaccard_index
FROM setdigest_side_by_side
ORDER BY id1, id2;

結果：

上記の結果リストは、予想通り、id 1と3のテキストがかなり類似していることを示しています。

id 2のテキストもid 1と3のテキストとある程度似ていると主張することができます。上記の例では、テキストの類似性を測定するために4文字のシングルが考慮されているため、テキストのペア1と2、および3と2の間には共通部分が見つからず、したがってこれらのテキストのペアの類似性指数は0です。

データ構造

Trinoは、以下のコンポーネントをカプセル化してSet Digestデータスケッチを実装しています：

• HyperLogLog
• 単一のハッシュ関数を使用したMinHash

HyperLogLog構造は、元のセット内の異なる要素の近似を行うために使用されます。

MinHash構造は、元のセットの低メモリフットプリントのシグネチャを格納するために使用されます。任意の2つのセットの類似性は、それらのシグネチャを比較することによって推定されます。

このデータ構造のTrinoタイプは、setdigestと呼ばれます。Trinoは複数のSet Digestデータスケッチをマージする機能を提供しています。

シリアライズ

データスケッチは、varbinary形式にシリアル化およびデシリアル化することができます。これにより、後で使用するためにデータを保存することができます。

関数