集合摘要函数¶

MinHash，或最小独立排列局部敏感哈希方案，是一种在计算机科学中用于快速估计两个集合相似度的技术。MinHash 作为一种概率数据结构，可以估计 Jaccard 相似系数 - 将两个集合的重叠部分占两个集合中所有唯一元素的百分比作为度量。Presto 提供了一些处理MinHash技术的函数。

MinHash 用于快速估计两个集合之间的Jaccard 相似系数。它通常用于数据挖掘，以大规模检测近似重复的网页。通过利用这些信息，搜索引擎可以有效地避免在搜索结果中显示两个几乎相同的页面。

数据结构¶

Presto 通过封装以下组件来实现集合摘要数据草图

• HyperLogLog

• 具有单个哈希函数的 MinHash

截至目前，HyperLogLog 和 MinHash 是 Presto 中实现或某些 Presto 函数用来处理大型数据集的技术。

HyperLogLog (HLL)：HyperLogLog 是一种用于估计集合基数的算法 - 即大型数据集中不同元素的数量。Presto 使用它来提供 approx_distinct 函数，该函数可用于估计列中不同条目的数量。

示例

SELECT approx_distinct(column_name) FROM table_name;

MinHash：MinHash 用于估计两个或多个集合之间的相似度，通常称为 Jaccard 相似度。在处理大型数据集时，它特别有效，通常用于数据聚类和近似重复检测。

示例

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()¶

返回对两个集合摘要的交集的基数的估计。

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()¶

返回对两个集合摘要的Jaccard 指数的估计。

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)¶

返回一个映射，其中包含属于 x 或 varchar 的内部 MinHash 结构中的Murmur3Hash128 哈希值及其出现次数。

x 的类型必须为 setdigest。

示例

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