集合ダイジェスト関数¶

MinHash、または最小値独立置換局所感度ハッシュスキームは、2つの集合がどれだけ似ているかを迅速に推定するためにコンピュータサイエンスで使用される手法です。MinHashは、ジャカード類似係数（2つの集合の重複を、両方の集合の総ユニーク要素に対する割合として測定したもの）を推定する確率的データ構造として機能します。Prestoは、MinHash手法を扱ういくつかの関数を提供します。

MinHashは、2つの集合間のJaccard類似係数を迅速に推定するために使用されます。これは、大規模なデータマイニングで、ほぼ重複したウェブページを検出するために一般的に使用されます。この情報を使用することで、検索エンジンは、検索結果にほぼ同一の2つのページを表示することを効率的に回避できます。

データ構造¶

Prestoは、以下のコンポーネントをカプセル化することにより、集合ダイジェストデータスケッチを実装します。

• HyperLogLog

• 単一のハッシュ関数を持つMinHash

現在、HyperLogLogとMinHashは、Prestoに実装されているか、またはPrestoの特定の関数で大規模なデータセットを処理するために使用されている手法です。

HyperLogLog (HLL)：HyperLogLogは、集合の基数（つまり、大規模なデータセット内の異なる要素の数）を推定するために使用されるアルゴリズムです。Prestoでは、これを用いて、列内の異なるエントリ数を推定するために使用できるapprox_distinct関数を提供しています。

例

SELECT approx_distinct(column_name) FROM table_name;

MinHash：MinHashは、ジャカード類似度として一般的に知られている、2つ以上の集合間の類似度を推定するために使用されます。大規模なデータセットを扱う場合に特に効果的で、一般的にデータクラスタリングや近似重複検出で使用されます。

例

WITH mh1 AS (SELECT minhash_agg(to_utf8(value)) AS minhash FROM table1), mh2 AS (SELECT minhash_agg(to_utf8(value))
AS minhash FROM table2), SELECT jaccard_index(mh1.minhash, mh2.minhash) AS similarity FROM mh1, mh2;

このデータ構造のPresto型はsetdigestと呼ばれます。Prestoは、複数の集合ダイジェストデータスケッチをマージする機能を提供します。

シリアライゼーション¶

MinHashやHyperLogLogの使用によって作成されたようなデータスケッチは、varbinaryデータ型にシリアライズできます。これらのデータ構造をシリアライズすることで、効率的に格納し、必要に応じて異なるシステムやセッション間で転送できます。格納後は、再度使用が必要になったときに元の状態にデシリアライズできます。Prestoのコンテキストでは、通常、これらのデータスケッチをバイナリとの間で変換する関数を使用してこれを行います。例としては、to_utf8()またはfrom_utf8()の使用が挙げられます。

関数¶

make_set_digest(x) -> setdigest()¶

xのすべての入力値をsetdigestに合成します。

例

Create a ``setdigest`` corresponding to a ``bigint`` array::

SELECT make_set_digest(value)
FROM (VALUES 1, 2, 3) T(value);

Create a ``setdigest`` corresponding to a ``varchar`` array::

SELECT make_set_digest(value)
FROM (VALUES 'Presto', 'SQL', 'on', 'everything') T(value);

merge_set_digest(setdigest) -> setdigest()¶

個々のsetdigest構造の集計和集合のsetdigestを返します。

例

SELECT merge_set_digest(a) from (SELECT make_set_digest(value) as a FROM (VALUES 4,3,2,1) T(value));

cardinality(setdigest) -> bigint()¶

内部HyperLogLogコンポーネントから集合ダイジェストの基数を返します。

例

SELECT cardinality(make_set_digest(value))
FROM (VALUES 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5) T(value);
-- 5

intersection_cardinality(x,y) -> bigint()¶

2つの集合ダイジェストの共通部分の基数の推定値を返します。

xとyはsetdigest型である必要があります。

例

SELECT intersection_cardinality(make_set_digest(v1), make_set_digest(v2))
FROM (VALUES (1, 1), (NULL, 2), (2, 3), (3, 4)) T(v1, v2);
-- 3

jaccard_index(x, y) -> double()¶

2つの集合ダイジェストのJaccard indexの推定値を返します。

xとyはsetdigest型である必要があります。

例

SELECT jaccard_index(make_set_digest(v1), make_set_digest(v2))
FROM (VALUES (1, 1), (NULL,2), (2, 3), (NULL, 4)) T(v1, v2);
-- 0.5

hash_counts(x) -> map(bigint, smallint)¶

Murmur3Hash128でハッシュされた値と、xまたはvarcharに属する内部MinHash構造内の出現回数のカウントを含むマップを返します。

xはsetdigest型である必要があります。

例

SELECT hash_counts(make_set_digest(value))
FROM (VALUES 1, 1, 1, 2, 2) T(value);
-- {19144387141682250=3, -2447670524089286488=2}