Set Digest 함수

Set Digest 함수는 MinHash 기법을 다루는 함수들이에요. 두 집합 사이의 Jaccard 유사도 계수를 빠르게 추정할 때 써요.

출처: 문서

본문

Trino는 MinHash 기법을 다루는 여러 함수를 제공해요.

MinHash는 두 집합 사이의 Jaccard 유사도 계수를 빠르게 추정하는 데 사용돼요. 데이터 마이닝에서 규모에 따라 거의 중복된 웹 페이지를 감지하는 데 흔히 쓰여요. 이 정보를 통해 검색 엔진은 거의 동일한 두 페이지를 검색 결과에 함께 표시하지 않도록 효율적으로 피해요.

다음 예제는 Set Digest 함수로 텍스트 간 유사도를 추정하는 방법을 보여줘요. 입력 텍스트는 ngrams() 함수로 4-shingle로 분리되고, 이는 각 초기 텍스트의 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-shingle을 고려했기 때문에 텍스트 쌍 1-2, 3-2에서는 교집합이 발견되지 않아 유사도 지수가 0이에요.

데이터 구조 (Data structures)

Trino는 Set Digest 데이터 스케치를 다음 구성 요소로 캡슐화해 구현해요.

HyperLogLog
단일 해시 함수를 쓰는 MinHash

HyperLogLog 구조는 원래 집합의 고유 요소 근사에 사용돼요. MinHash 구조는 원래 집합의 낮은 메모리 풋프린트 시그니처를 저장하는 데 사용돼요. 두 집합의 유사도는 두 시그니처를 비교해 추정해요.

Trino에서 이 데이터 구조의 타입은 setdigest라고 해요. Trino는 여러 Set Digest 데이터 스케치를 병합하는 기능도 제공해요.

직렬화 (Serialization)

데이터 스케치는 varbinary로 직렬화·역직렬화할 수 있어요. 나중에 쓸 수 있게 저장할 수 있죠.

함수 (Functions)

make_set_digest(x) → setdigest

x의 모든 입력 값을 하나의 setdigest로 구성해요.

bigint 배열에 해당하는 setdigest 만들기:

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

varchar 배열에 해당하는 setdigest 만들기:

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

내부 HyperLogLog 구성 요소에서 set digest의 카디널리티를 반환해요.

예:

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에 대한 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)

x에 속한 내부 MinHash 구조 안의 Murmur3Hash128 해시 값과 그 발생 횟수를 담은 map을 반환해요.

x는 setdigest 타입이어야 해요.

예:

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

더 알아보기 (Learn more)

Set Digest는 MinHash와 HyperLogLog를 결합한 구조예요. HyperLogLog 기반 함수는 HyperLogLog 함수 문서에서 더 볼 수 있어요.