LogLog: 서로 다른 값의 개수를 추정하는 방법

Linear Counting과 Min Value를 다룬 앞의 글들에 이어, 드디어 데이터에 들어 있는 서로 다른 값의 개수를 추정하는 확률적 알고리즘 가운데 거의 최고라고 할 만한 LogLog를 살펴보자. 이보다 나은 것은 LogLog에서 나온 동생 격인 HyperLogLog뿐인데, 그것은 다음 글에서 다룬다.

문제를 다시 정리하자. 입력으로 어떤 데이터 또는 중복집합, 예를 들어 ID의 배열이나 생성기가 주어진다. 이 배열에는 여러 번 나오는 값이 있고, 배열에 들어 있는 서로 다른 값의 개수를 구하려고 한다. 이 개수를 카디널리티라고 한다. 카디널리티가 정말 크다고 가정한다. 그렇지 않으면 보통의 알고리즘을 쓰면 된다.

LogLog 알고리즘의 아이디어

이진 벡터의 집합이 있다고 하자. 겁먹을 필요는 없다. 예를 들어 0001011001001100은 길이가 16인 이진 벡터이다. 길이가 32인 이진 벡터가 모두 100만 개 있고, 모두 완전히 무작위로 만들어졌다고 하자. 0으로 끝나는 벡터는 몇 개일까?

물론 정확히 알 수는 없지만, 벡터를 정말 무작위로 만들었다면 대략 절반, 즉 50만 개가 0으로 끝날 것이다. 00으로 끝나는 벡터는 몇 개일까? 4분의 1이다. 000으로 끝나는 벡터는? 8분의 1이다. 이런 식으로 계속된다. 대략 다음과 같이 나타낼 수 있다.

벡터의 꼴          전체 벡터 중 비율
...xxxxxx0        50%
...xxxxx00        25%
...xxxx000        12.5%
...xxx0000        6.25%
     ...          ...

길이가 d인 접미사(접미사는 다른 문자열의 끝부분을 이루는 문자열로, 접두사의 반대이다)를 생각하면, 이 접미사로 끝나는 벡터가 v개 있을 것으로 기대한다. v의 값은 다음과 같이 구한다.

$v = \frac{1}{2^{d}} \cdot N$

여기서 N은 집합에 있는 모든 벡터의 개수이다. 길이가 3인 접미사(예를 들어 …010)는 1/2^3 N = 1/8 N개의 벡터, 즉 전체 벡터의 12.5%에 나타나야 한다.

이제 머리가 띵해지는 이야기를 해 보자. 서로 다른 벡터 1,024개로 이루어진 중복집합이 있다고 하자. 접미사 0000000000(0이 10개)으로 끝나는 벡터는 몇 개여야 할까? 식에 대입하면 다음과 같다.

$v = \frac{1}{2^{10}} \cdot 1024 = \frac{1}{1024} \cdot 1024 = 1$

오, 하나이다! 무작위로 만든 이진 벡터 약 1,000개 중에서 0 10개로 끝나는 벡터는 하나여야 한다. 이 정보로 서로 다른 원소의 개수를 어떻게 추정할 수 있을까? 거꾸로 생각하면 된다. 입력으로 주어진 이진 벡터를 모두 훑었더니 0 10개로 끝나는 벡터가 하나뿐이라면? 그러면 집합에 벡터가 1,024개 있었다고 추정할 수 있다!

일반화하여 알고리즘 만들기

목표는 한 벡터에만 들어 있으면서 될 수 있는 대로 짧은 접미사를 찾는 것이다. 하지만 이런 접미사를 찾기는 매우 어렵다. 그런 벡터를 정말로 찾으려면 모든 접미사를 저장해야 하는데, 그러면 메모리를 너무 많이 차지하기 때문이다. 그 대신 벡터 끝에 있는 0의 가장 긴 연속을 찾는 것으로 만족하자.

따라서 모든 벡터를 훑으면서 벡터마다 끝에 0이 몇 개 있는지 세고, 그 값의 최댓값을 변수 하나에 저장한다. 모든 벡터를 훑고 나면 0으로만 이루어진 가장 긴 접미사의 길이를 알게 된다. 이 길이를 문자 d로 나타낸다. 이제 앞의 식을 고쳐 변수 N을 따로 떼어 낸다. 즉 N을 알고리즘의 입력이 아니라 출력으로 만든다. 이때 그런 벡터가 하나 있을 것으로, 즉 v=1이 성립할 것으로 기대하므로 v에 1을 대입한다.

$\begin{array}{rcl} v & = & \frac{N}{2^{d}} \\ v \cdot 2^{d} & = & N \\ 2^{d} & = & N \end{array}$

따라서 0으로만 이루어진 가장 긴 접미사의 길이 d를 찾으면 식 N=2^d로 카디널리티를 추정한다.

무작위 이진 벡터는 어떻게 얻을까

무작위 이진 벡터에 대해서는 알고리즘이 동작한다. 그러면 이 방법을 실제 데이터에는 어떻게 적용할까? 늘 그렇듯이 여기서도 알맞은 해시 함수를 쓴다. 입력 데이터, 예를 들어 ID(문자열)가 주어지면 먼저 해싱한다. n비트 해시 함수의 출력은 n개의 비트이고, 실용적인 관점에서 이 비트들은 무작위로 만든 이진 벡터처럼 보인다.

이제 알고리즘을 쓸 수 있다.

def trailing_zeroes(number):
    if number == 0: 
        return 0

    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def count_unique(values):
    max_zero_suffix_length = 0
    for value in values:
        zeroes_length = trailing_zeroes(hash(value))
        max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

함수 trailing_zeroes는 수의 끝에 있는 0의 개수를 돌려준다. 어떻게 동작할까? 코드를 보고 이해하지 못했다면 차라리 묻지 않는 편이 낫다. 함수의 성능은 어떨까? 서로 다른 원소가 10만 개인 집합에 대해 함수는 추정값 524,288을 돌려주었다.

음…

썩 좋지는 않다. 하지만 괜찮다! 앞의 Min Value와 똑같은 방법으로 알고리즘을 개선해 보자. 입력 데이터를 서로소인 그룹 여러 개로 나누고, 그룹마다 0으로만 이루어진 가장 긴 접미사의 길이를 구한 다음, 마지막에 그 평균 길이를 구해 서로 다른 값의 개수를 추정한다.

예를 들어 각 벡터의 마지막 두 비트가 벡터가 속한 그룹의 번호를 정한다고 하자. 다음 벡터 6개는

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

끝부분에 따라 그룹 4개로 나눌 수 있다.

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

다음으로 각 벡터에서 0으로만 이루어진 가장 긴 접미사의 길이를 구한다. 단, 그룹 번호로 쓴 비트는 건너뛴다. 0으로 이루어진 “접미사”는 초록색으로 표시했다.

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

마지막에 적은 것이 각 그룹의 가장 긴 0 접미사의 길이이다. 이 값들의 산술평균을 구하면 2.75이다. 이 값을 식에 대입하면 다음과 같다.

$2^{2.75} ≒ 6.727$

이것이 각 그룹에 들어 있는 서로 다른 원소의 평균 개수이다. 물론 전혀 맞지 않지만 신경 쓰지 말자. 작은 집합에 대해서는 LogLog 알고리즘의 결과가 형편없다.

집합 전체의 카디널리티를 추정하려면 이 값에 그룹의 개수를 곱해야 한다. 즉 6.727 · 4 = 26.908이다. 알고리즘은 집합에 서로 다른 값이 약 27개 있다고 계산했다. 실제로는 6개였으니 완전히 빗나갔지만, 지금은 정말 상관없다.

알고리즘의 구현

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets

매개변수 k는 몇 비트를 그룹의 인덱스로 쓸지 정한다. 이 매개변수가 알고리즘의 정확도를 정한다. k가 클수록 더 정확하다. 변수 bucket_index에는 그룹 번호가 저장된다. 등호 오른쪽의 마법은 어떻게 동작할까?

변수 num_buckets에는 그룹의 개수가 들어 있는데, 이 값은 언제나 2의 거듭제곱이다. 예를 들어 k = 3이면 num_buckets=8이다. 수 8은 이진법으로 1000이다. 여기서 1을 빼면 수 7, 즉 0111이 된다. num_buckets에서 1을 빼면 언제나 끝에 1이 k개 있고 그 앞은 모두 0인 수를 얻는다. 다음으로 논리곱(연산자 &)을 계산한다. 벡터 1110110010100101에 대해 이 연산은 다음과 같다.

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

이 마법의 목적은 앞부분은 모두 0이고 마지막 k비트는 해시값 h와 같은 수를 얻는 것이다.

다음으로 bucket_hash를 계산한다. 이 값은 원래 해시값 전체를 오른쪽으로 k비트만큼 시프트하여 마지막 k비트를 없앤 것이다. 시프트는 수의 모든 비트를 오른쪽으로 k비트만큼 옮기고 왼쪽을 0으로 채운다. (오른쪽으로 1비트 시프트하는 것은 수를 2로 나누고 나머지를 버리는 것과 같다.) 벡터 1110110010100101을 3비트 시프트하면 0001110110010100을 얻는다. 이 벡터가 변수 bucket_hash에 저장된다.

다음으로 이 벡터의 끝에 있는 0의 개수를 세고, 이 값이 배열 max_zeroes의 인덱스 bucket_index에 저장된 현재 최댓값보다 크면 값을 덮어쓴다.

마지막으로 모든 그룹에서 0의 평균 개수를 구하고, 각 그룹에 들어 있는 서로 다른 원소의 평균 개수(2 ** average_max_zeros)를 구한다. 그룹은 모두 num_buckets개이므로 이 값에 그룹의 개수를 곱하면 서로 다른 원소의 개수에 대한 최종 추정값을 얻는다. 휴, 어렵지 않았다. 서로 다른 값이 25만 개 들어 있는 여러 데이터에 대해 k=10으로 얻은 결과는 다음과 같다.

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

으아, 아직도 틀렸다 :-(. 하지만 걱정하지 말자. 이제 꽤 가까워졌다. 모든 결과가 정답보다 크다는 점에 주목하자. 알고리즘이 진행되는 동안 여러 오차가 쌓여서 추정값이 정답보다 눈에 띄게 커진다. 하지만 이 오차는 비교적 일정하므로 오차가 얼마나 되는지 추정할 수 있다. 추정값에 경험적으로 정한 마법의 수 0.79402를 곱하면 훨씬 나은 결과를 얻는다.

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

카디널리티가 100만인 중복집합으로도 시험해 보았다. 결과는 다음과 같다.

결과                   오차
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

아주 좋다! 오차가 2.5% 아래이므로 꽤 괜찮은 성능이다. 이것이 LogLog 알고리즘이다. 마법의 수까지 넣은 최종 구현은 다음과 같다.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets * 0.79402

이 알고리즘을 어떻게 고치면 전설적인 최고의 알고리즘 HyperLogLog가 되는지는 다음 글에서 다룬다. 지금은 알고리즘의 메모리 사용량을 살펴보자.

메모리 사용량

이 알고리즘은 메모리를 매우 효율적으로 쓴다. 기억해야 할 것은 최댓값을 저장하는 배열 하나뿐이다. 이 배열의 길이는 k의 값, 즉 벡터에서 그룹 인덱스로 쓰는 비트 수에 따라 정해진다. 주어진 k에 대해 그룹은 모두 2^k개이므로 최댓값 배열의 길이는 2^k이다. 이 값을 구현에서는 num_buckets라고 불렀다.

배열의 한 칸은 얼마나 커야 할까? 칸에는 0으로만 이루어진 접미사의 길이를 저장한다. 미리 말하자면 64비트 해시값이면 아마 세상에서 생각할 수 있는 모든 중복집합에 충분할 것이다. 따라서 이 배열에는 0(모든 비트가 1인 벡터)부터 64(모든 비트가 0인 벡터)까지의 수를 저장할 수 있어야 한다. 또 k가 언제나 0보다 크다고 가정하면 0부터 63까지의 수만 저장하면 된다. 2⁶ = 64이므로 6비트면 충분하다.

그렇다. 한 칸의 크기가 6비트인 “배열”이면 충분하다. 또 k=10이면 수억 단위의 카디널리티까지 꽤 정확하게 추정할 수 있다. 이렇게 설정한 알고리즘은 크기가 2¹⁰ = 1024이고 각 칸이 6비트를 차지하는 배열을 만든다. 이 배열은 모두 6,144비트, 즉 768바이트를 차지한다. 1킬로바이트도 되지 않는다.

이것이 전부이다.

다른 것은 저장할 필요가 없다. 계산한 해시값은 바로 버려도 되고, 벡터 끝에 있는 0의 개수만 알면 된다.

예를 들어 128비트를 돌려주는 더 큰 해시 함수를 쓰더라도 메모리 사용량은 크게 바뀌지 않는다는 점에 주목하자. 0부터 127까지의 수를 저장하면 되므로 7비트면 충분하다. 따라서 메모리 사용량은 주로 매개변수 k, 즉 그룹의 개수가 정한다.

LogLog는 카디널리티가 정말 큰 중복집합의 원소를 셀 때 특히 알맞다. 위의 간단한 예에서도 보았듯이 LogLog는 카디널리티가 작은 중복집합을 잘 다루지 못한다. 하지만 이것도 해결할 수 있다. 예를 들어 중복집합의 카디널리티가 작다는 것을 알게 되면 앞에서 설명한 Linear Counting 같은 다른 알고리즘으로 추정하면 된다. 이 이야기도 다음 글에서 다룬다.

참고 자료:

Loglog Counting of Large Cardinalities [PDF]
Damn Cool Algorithms: Cardinality Estimation(LogLog 코드는 대부분 여기서 가져왔다)

목차: Linear Counting: 서로 다른 값의 개수를 추정하는 방법, Min Value: 서로 다른 값의 개수를 추정하는 방법, LogLog: 서로 다른 값의 개수를 추정하는 방법, HyperLogLog: 서로 다른 값의 개수를 매우 정확하게 추정하는 방법

« 이전: Min Value: 서로 다른 값의 개수를 추정하는 방법

다음: HyperLogLog: 서로 다른 값의 개수를 매우 정확하게 추정하는 방법 »