Probabilistic Data Structures for Web Analytics and Data Mining

이런 훌륭한 글이 있군요. 위 글은 많은 양의 데이터에서 각 아이템의 출현횟수를 세거나 unique 아이템의 수가 몇개인지 세거나 하는 방법들입니다. 예를들어 integer가 엄청나게 많을때 각 값의 출현횟수 세기같은 경우죠.

간단하게 관심가는 것들, 기본적인 내용으로 정리해봅니다.

1. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Linear Counting
m 비트를 준비합니다. 주어진 입력을 0~(m-1) 사이로 해싱합니다. 그 다음 해당 비트의 값을 1로 셋팅. 결국 1로 셋팅된 비트의 수를 세면 이게 입력에 있는 unique한 숫자의 갯수가 되겠죠.

2. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Log Log Counting
전에 대량의 데이터에서 대략적으로 UNIQUE ITEM 의 수 세기에서 썼던 내용입니다. 다시 정리하자면, 주어진 입력을 해싱함. 해싱한 수들을 살펴보고 제일 앞자리에 최대 몇개의 0이 연속으로 나오는지 봅니다. 이 때 최대 r자리의 연속된 0을 봤다고 하면 2^r개의 unique item이 있구나 하고 보는 방법입니다.

이유는 간단하죠. 해시값의 제일 앞자리에 0이 나올려면 2개의 unique숫자를 봤어야합니다. 1개만 봤을때는 앞자리가 1일수 있으니까요. 마찬가지로 해시값 앞자리에 연속된 0이 2개, 즉 00이 나오려면 4개의 unique숫자를 봤어야합니다. 예를들어 3개만 봤다면 해시값 앞자리가 11, 10, 01이었을 수 있으까요.

사실 2^r은 너무 거친 추정이므로 여러개의 해시함수를 써서 평균을 내던가 하는 방법을 씁니다.

3. 각 입력의 출현횟수 세기: Count-Min Sketch
대량의 데이터에서 각 입력값이 몇번 나왔나 세는 방법입니다. 예를들어 integer로 구성된 데이터였다면 1은 몇개나왔나, 2는 몇개나왔나 등을 세는 것이죠.

방법은 이렇습니다. 0으로 초기화된 d행 w열의 행렬 m을 준비합니다. 그리고 해시 함수 d개를 준비합니다. 이들을 각각 h_1, h_2, …, h_d 라고 합시다. 이 해시는 각각 0~(w-1)까지의 숫자로 입력을 해싱해 줍니다. 처리할 대량의 데이터에대해 다음을 수행합니다.

for each of datum in input
  for i in 1..d
    m[i, h_i(datum)] += 1
  end for
end for

자 그러면 각 입력에대해 총 d개 셀을 1씩 추가시키는 것이죠.

이게 끝나고나서, 역으로 어떤 숫자 k의 출현횟수를 세고 싶다고 하면 다음과 같이 k의 출현횟수를 찾습니다.

cnt = INT_MAX
for i in 1..d
  cnt = min(cnt, m[i, h_i(k)])
end for

여기서 min이 필요한 이유는 이 방법이 본질적으로 hash collision이 있기 때문에 항상 count를 overestimate하기 때문입니다.

4. Range Query: 다수의 Count-Min Sketch 사용
Count-Min Sketch로 어떤 수 k가 몇회나왔는가는 잘 셀수 있게 되었습니다. 이번엔 range query로 1, 2, 3, .., k 까지의 수가 몇번 나왔나? 혹은 500, 501, …, k까지의 수가 몇회나왔나? 와 같은 질문이 주어졌을때 답하는 방법입니다.

이는 Count-Min Sketch만으로는 부족합니다. 각 숫자의 출현횟수를 매번 구하기가 어려울 수 있으니까요. 이를 위해 Count-Min Sketch를 여러개 쓸 수 있습니다. 예를들어 일단 기본적인 Count-Min Sketch를 만듭니다. 그다음은 1, 2를 하나의 수로 3,4를 하나의 수로, … 과 같이 연속된 2개씩의 숫자들을 카운트를 세는 Count-Min Sketch를 만듭니다. 거기에더해 1~4, 5~8, … 과 같이 연속된 4개의 숫자를 묶어서 세는 Count-Min Sketch를 만듭니다. 이런식으로 계속해서 2배씩 키워나가는 Count-Min Sketch를 많이 만듭니다.

이걸로 range query를 어떻게 처리할지 벌써 감이 오시죠?

예를들어 1, 2, 3, …, 10 의 총 발생횟수는 1~8, 9~10 의 2개의 Count-Min Sketch로 답합니다. 또 다른 예로 1~6의 발생횟수는 1~4, 1~2의 2개로 답하면 되겠죠.

5. 집합에 속해있는지. Bloom Filter.
아주 많은 숫자들의 집합이 있습니다. 어떤 입력이 주어졌을때 그 수가 집합의 원소인지 빠르게 답하는 방법이 바로 bloom filter입니다. 방법은 이렇습니다.

m 비트를 만들고 각 자리를 0으로 초기화합니다. 그리고 n 개 해시 함수 h_1, h_2, …, h_n을 만들어놓습니다. 그 다음 집합에 속해있는 데이터에 대해서 다음을 수행합니다.

for each of datum in input
  for i in 1..n
    m[h_i(datum)] = 1
  end for
end for

결국 각 데이터에 대해 n개의 해시함수를 적용해서 각 자리를 1로 셋팅하는 것이죠. 다 준비가 되면 각 입력에 대해 다음을 수행하면 그 입력이 집합에 속하는지 알 수 있습니다.

is_member = true
for i in 1..n
  is_member = is_member && m[h_i(input)]
  if !is_member
    return false
  end if
end for
return true

물론 hash collision이 있기에 이 방법은 false positive가 있습니다.

앞서의 방법들 모두 오차가 있습니다. 그 오차의 한계를 관리하기위해 m, n, d, w 등의 파라미터를 잘 정해주어야 합니다.