Функции Set Digest

CedrusData предоставляет ряд функций, для работы с MinHash.

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

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

Следующий пример демонстрирует, как функции 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

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

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

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

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

• HyperLogLog

• MinHash с одной хэш-функцией

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

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

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

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

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

Функции

make_set_digest(x) → setdigest

Формирует setdigest из всех входных значений x.

Создание 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, являющийся агрегатным объединением отдельных структур 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

Возвращает оценку индекса Жаккара для двух 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}