DGIM Algorithm

DGIM Algorithm은 Sliding Window 방법에서 0과 1의 스트림이 입력값으로 들어올 때, 가장 최근의 N개의 데이터에서 1이 몇개 있는지를 예측하는 알고리즘이다. 여기서  Sliding Window 란, 빅데이터의 스트림들을 처리할 때 모든 데이터를 저장하지 않고, 순차적으로 n개의 데이터들을 미끄러지듯이 확인하는 방법이다. 시간순으로 들어오는 데이터들을 마치 창문이 미끄러지듯이 읽으면서 질의에 대응하는 모습 때문에  이런 이름이 붙었다 

 

 

sliding window의 모습 위의 보라색으로 색칠된 부분이 n개의 데이터를 갖는 윈도우 이다. 윈도우는 시간에 따라 앞으로 나아가는 성질을 가지고 있다. 

 

Counting Bits

Counting Bits 문제는 Sliding Window 개념을 응용해서 k<=N 일때, 0과 1로 이루어진 스트림중 가장 최근의 k bits 에서 1의 개수를 헤아리는 문제이다. 가장 명백한 정답은 최근 N개의 데이터를 모두 저장하는 방법을 통해 구할 수 있다. 이 경우에, 새로운 비트가 들어오면 가장 오래 전에 들어온 비트를 제거함으로써 N개의 데이터를 유지하고 1의 개수를 갱신해서 대답할 수 있다. 

 

하지만, 실제 상황에서의 문제는 N개의 데이터를 모두 저장할 수 없는 경우에 발생한다. 

이를 개선하기 위해 등장한 알고리즘이 바로 DGIM Algorithm이다.  이 알고리즘은 N개의 window의 1의 개수를 세기 위해 O(N) 의 메모리가 아닌, O(log^2 N) 의 공간만을 요구하기 떄문에 근사적인 1의 개수를 메모리의 관점에서 훨씬 더 효과적으로 예측할 수 있다.

 

예를 들어, Sliding Window를 구성하는 데이터의 개수가 2^100인 경우 1000^10의 공간이 아닌, 10,000의 상수배의 메모리만을 차지하는 셈이니 굉장히 메모리를 절약할 수 있게 된다. 에러는 최대 50%로 작은 편은 아니다 (왜 최대 50%인지는 뒤에서 설명하겠다.)

 

알고리즘은 굉장히 단순하다.

 

 

N개의 스트림 데이터들을 Bucket으로 분류한다. (위 그림에서 박스친 부분들이 각각의 Bucket)

이 버킷들은 다음의 특징을 만족해야 한다.

 

1. 각각의 버킷은 겹쳐서는 안된다. 

2. 버킷은 시간이 최근일수록 (timestamp가 클수록) 작거나 같아져야 한다. 즉, 오른쪽에 있는 버킷이 왼쪽의 버킷보다 클 수 없다.

3. 버킷의 크기는 2의 거듭제곱이어야 하며 (1, 2, 4, ....) 같은 크기를 갖는 버킷은 최대 2개까지여야 한다.

 

이러한 버킷을 가지고 1의 개수를 예측하는 방법은 간단하다. 위에 제시된 예제를 통해 연습해보면 다음과 같다.

1의 개수의 버킷이 2개이므로 2

2의 개수의 버킷이 1개이므로 2

4의 개수의 버킷이 2개이므로 2 * 4 = 8

8의 개수의 버킷이 2개이므로 8 * 2 = 16

16의 개수의 버킷은 N의 범위 밖에 있으므로 16/2 = 8 (버킷의 크기 / 2 로 근사시켜 구한다.)

 

즉 DGIM Algorithm을 통해서 위 예제의 1의 개수를 근사적으로 구하면 2+2+8+16+8 = 36개이다.

 

Storage Requirement

각각의 Bucket은 1의 개수와 timestamp를 저장하는데 이들 모두를 저장하는데 O(logN) bits를 요구한다.

(A) timestamp는 1부터 N까지만 기록된다. (가장 최근의 timestamp는 0, timestamp는 가장 오래된 비트를 1로 놓고 N으로 Modular 연산한 값을 저장한다.) 따라서 이들을 기록하기 위해서는 O(logN)의 비트만 있으면 된다. 0~2^n-1의 수를 저장하기 위해서는 n개의 비트만 있으면 되기 때문이다.

 

(B) number of 1s 를 저장하기 위한 비트의 개수는 O(log log N)개이다. 맨처음에 이를 이해하는게 꽤 어려움을 겪었지만, 힌트는 각각의 버킷에 있는 1의 개수가 2의 Power라는데에서 찾을 수 있다. 

예를 들어 3번 버킷에서 1의 개수가 8개라면, 이를 저장하기 위해 3개의 비트를 쓸 필요가 없다는 이야기다.

왜냐하면 모든 버킷에서 1의 개수는 2의 거듭제곱이기 때문에 8을 저장하기 위해서는 3을 저장하면 된다는것이다. 

16을 저장하기 위해서는 4만 저장하면 되고, 결국 log N개의 숫자만을 표현할 수 있으면 된다. 따라서 log N 개의 비트를 표현하기 위해서 log log N 개의 비트가 있으면 된다는 것이다. 

 

따라서 하나의 버킷을 저장하는데 필요한 공간복잡도는 O(log N) + O(log log N) = O(log N)이 된다.

전체 버킷의 수는 O(log N) 이므로 1의 개수를 예측하기 위해서 필요한 저장공간은 O(log N) * O(log N)이 되는 것이다. 

(전체 버킷의 수가 O(log N)이 되는 것은 하나의 버킷이 최소 2^k승만큼의 크기를 갖는다는 것에서 증명해 낼 수 있다.)

 

 

Updating Buckets

버킷을 업데이트 한다는 것은 스트림에 새로운 원소 (위 문제의 경우 0 또는 1) 이 들어왔다는 것을 의미한다.

새로운 원소가 0 또는 1이므로 2가지 경우로 나누어 생각해볼 수 있다.

 

1. 0이 들어오는 경우

버킷에는 영향을 주지 않으므로 더 이상의 변화는 필요하지 않다.

 

2. 1이 들어오는 경우

새로 들어온 1을 크기 1인 버킷으로 만든다.

만일 이때, 크기가 1인 버킷이 이미 2개가 있었다면, 그 2개의 버킷을 합쳐서 크기가 2인 버킷으로 만든다.

그런데 만약 이렇게 했을 때, 크기가 2인 버킷이 3개가 생긴다면 마찬가지로 오래된 2개의 버킷을 합쳐서 크기가 4인 버킷으로 만든다.

이를 반복하여 스트림의 버킷들을 갱신해주면 된다. 

 

버킷의 갱신 과정

 

 

 Error Bound

 

앞서 DGIM Algorithm 의 Error bound 가 50% 라고 설명한 바 있다. 이를 증명해보도록 하자.

마지막 버킷의 크기를 2^r 라고 하면, (여기서 마지막 버킷이란, N의 범위를 넘어가 잘리는 버킷을 의미한다.)

우리는 그 버킷에 들어있는 1의 개수를 2^(r-1)이라 가정하고 1의 개수를 예측한다 .

즉, 우리는 예측할 때 윈도우 안에서, 최대 2^(r-1)만큼의 오차를 낼 수 있는 것이다. (다 0인데, 절반이 1이라고 예측하는 경우 오차가 최대가 될 것이다.) 

 

이때, 윈도우 안에는 2^r보다 작은 개수의 1을 가지는 버킷들이 적어도 1개씩 존재한다. 다시 말해, 적어도 적어도 2^r-1개의 1이 윈도우 안에 존재한다는 것이다. (왜냐하면 1+2+4+...+2^(r-1) = 2^r - 1이기 때문이다. 

 

따라서 에러는 기껏해야 50%정도가 되는 것이다.