The Datar-Gionis-Indyk-Motwani (DGIM) algorithm

빅데이터(Bigdata) DGIM 알고리즘 정리

Binary stream: [ 0100101000010101011100001010 ... ]

"길이가 N인 바이너리 스트림에서 마지막 k(<N) 비트 이내에 1이 몇 개나 들어있는가?"

 위 같은 의문이 있을 때 N의 수가 작으면 아주 간단하게 답을 찾을 수 있다.

하지만 현실은 N이 무지막지하게 크다는 것이다.. 이럴때 위 질문의 해답을 어떻게 찾을 수 있을까?

그 방법으로 DGIM algorithm을 사용할 수 있다.

---

DGIM algorithm은 다음과 같은 원리를 따른다.

- 1이 나오면 크기가 1인 bucket을 만든다.

- 동일한 크기의 bucket이 세 개 만들어지면 old bucket 두 개를 병합한다.

- 반복

규칙

1. 가장 최근에 들어온 '1'은 항상 크기가 1인 bucket이다.

2. 모든 1은 bucket 안에 들어 있어야 한다.

3. 모든 bucket 사이즈는 2의 거듭제곱이다. ( 1, 2, 4, 8 ...)

4. bucket의 크기는 시간이 지날수록 증가하며 감소할 수 없다.

아래 예시를 보면 쉽게 이해할 수 있다.

같은 크기의 bucket이 세 개 생기면 오래된 두 bucket이 결합되는 것을 볼 수 있다.

이때 마지막 k 비트 내에 있는 1의 개수를 추정하는 방법은, 

- 가장 최근부터 k 번째에 있는 비트를 포함한 bucket을 찾는다.

- k 번째 비트를 포함한 bucket을 제외하고 가장 최근부터 생성된 bucket들의 크기를 모두 더한다.

- 더한 값에 k 번째 비트를 포함한 bucket 크기의 절반을 더하면 k비트 내에 있는 1의 개수를 실제 값과 비슷하게 추정 할 수 있다.

위 그림 처럼 k=9일 경우에,

k 번째 비트를 포함한 bucket을 제외하고 가장 최근부터 생성된 bucket들의 크기는

2+1+1 = 4

k 번째 비트를 포함한 bucket의 크기의 절반은

4/2 = 2

이므로 k=9 일 경우 DGIM으로 추정한 1의 개수는

4/2 + 2 + 1 + 1 = 6

이다. 위 경우에 실제 1의 개수도 6이므로 추정값 실제값이 동일하게 계산 되었다.

 

여기서 설명은 따로하지 않겠지만 계산을 해보면

추정 값이 항상 실제 값의 ± 50% 이내의 범위에서 나타난다.