Функции Set Digest#

Trino предоставляет несколько функций, работающих с техникой MinHash.

MinHash используется для быстрой оценки коэффициента сходства Жаккара между двумя множествами.

Он обычно применяется в data mining для обнаружения почти дублирующихся веб-страниц в больших масштабах. Используя эту информацию, поисковые системы эффективно избегают показа в результатах поиска двух почти идентичных страниц.

Следующий пример показывает, как функции Set Digest могут использоваться для наивной оценки сходства между текстами. Входные тексты разбиваются с помощью функции ngrams() на 4-shingles, которые используются как входные данные для создания set digest каждого исходного текста. Затем set digest сравниваются друг с другом, чтобы получить приближенную оценку сходства соответствующих исходных текстов:

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 as id1,
                m1.digest as digest1,
                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 != m2.id AND m1.id < 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;

 id1 | id2 | intersection_cardinality | jaccard_index
-----+-----+--------------------------+---------------
   1 |   2 |                        0 |           0.0
   1 |   3 |                        4 |           0.6
   2 |   3 |                        0 |           0.0

Приведенный выше результат показывает, как и ожидалось, что тексты с id 1 и 3 достаточно похожи.

Можно возразить, что текст с id 2 в некоторой степени похож на тексты с id 1 и 3. Поскольку в примере выше для измерения сходства текстов учитываются 4-shingles, для пар текстов 1 и 2, а также 3 и 2 пересечений не найдено, и поэтому индекс сходства для этих пар текстов равен 0.

Структуры данных#

Trino реализует скетчи данных Set Digest, инкапсулируя следующие компоненты:

Структура HyperLogLog используется для приближенной оценки количества различных элементов в исходном множестве.

Структура MinHash используется для хранения сигнатуры исходного множества с низким потреблением памяти. Сходство любых двух множеств оценивается сравнением их сигнатур.

Тип Trino для этой структуры данных называется setdigest. Trino предоставляет возможность объединять несколько скетчей данных Set Digest.

Сериализация#

Скетчи данных можно сериализовать в varbinary и десериализовать обратно. Это позволяет сохранять их для дальнейшего использования.

Функции#

make_set_digest(x) → setdigest#

Объединяет все входные значения x в один setdigest.

Создание setdigest, соответствующего массиву bigint:

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

Создание setdigest, соответствующего массиву varchar:

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

merge_set_digest(setdigest) → setdigest#: Возвращает setdigest агрегированного объединения отдельных структур Set Digest setdigest.

cardinality(setdigest) → long

Возвращает мощность set digest на основе его внутреннего компонента 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) → long#

Возвращает оценку мощности пересечения двух set digest.

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 index для двух set digest.

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, содержащий хеш-значения Murmur3Hash128 и количество их вхождений во внутренней структуре MinHash, относящейся к x.

x должен иметь тип setdigest.

Примеры:

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