DGIM Algoritm

Sliding Window

 

Sliding window는 가장 최근의 N개의 element를 프로세싱할 때 유용한 방법이다. 정해진 기간 내의 데이터만 필요하거나 오래된 데이터는 필요 없을 경우, 또는 전체 데이터를 querying하는 것이 실용적이지 못할 때 sliding window를 사용한다.

 

N = 6

 

위 사진처럼 창문이 미끌어지듯 순차적으로 시간순으로 들어오는 데이터를 확인하기 때문에 sliding window라는 이름이 붙었다. 

 

 

Counting Bits

 

counting bits문제는 0과 1의 stream data가 들어왔을 때 최근 k개의 bits 중에서 1의 개수가 몇 개인지 세는 문제이다. (k <= N) obvious하게 N개의 bit를 모두 저장하고 새로운 비트가 들어오면 N+1의 비트(가장 오래된 비트)는 제거하고 1의 개수를 갱신하면 된다. 하지만 현실에서는 N개의 데이트를 모두 저장하는 것이 불가능하다.

 

 

(1) Simple Solution

 

최근 N개의 비트를 모두 저장하는 것이 불가능하므로, N개 중에 1의 개수가 몇개인지 대략적인 값만 estimate하기 위해 2개의 counter를 유지하자.

 

s : number of 1s from the beginning of the stream (1의 개수)

z : number of 0s from the beginning of the stream (0의 개수)

 

 

그렇다면 최근 N개의 비트 중 1개의 개수는 N * ( s / s +z )가 될 것이다. 

 

결국 N개의 window의 1의 개수를 세기 위해 O(N)의 메모리를 요구하게 된다.

하지만 이러한 방식은 0과 1의 stream data가 non-uniform하지 않을 때는 적용할 수 없다.

 

 

(2) Exponential Windows

 

 

 

Idea : 

• 하나의 bit가 들어오면, 사이즈가 1인 bucket을 하나 만든다
• 같은 level의 bucket이 3개가 되면, 가장 오래된(leftmost) 2개의 bucket을 합쳐 higher level로 올린다.
• 이러한 과정을 반복한다.
•  

Exponential window 방법은 logN개의 count 당 log N개의 bit가 필요 하므로 O(log^2N)만큼의 메모리를 필요로 한다. 또한 새로운 bit가 들어올 때마다 count를 업데이트를 간단히 할 수 있다. 하지만 이러한 방식은 N의 boundary 밖에 1이 모두 있는 not evenly한 case라면 error가 최소한 50%를 넘지않는다고 말할 수 없다.

 

DGIM Algorithm

 

DGIM Algorithm은 distribution의 uniformity를 가정하지 않는다.

 

 

Idea :

• bucket 사이즈를 bit 사이즈로 하는 것이 아닌 1의 개수로 한다.
• 선후관계를 나타내기 위해 각 bit는 timestamp를 가진다. 

 

각 버킷들의 특징

• bucket은 서로 not overlap 
• bucket size는 2의 제곱승이어야 하며, 같은 크기를 갖는 bucket은 1개 또는 2개이다.
• 왼쪽에 있는 bucket일 수록 그 크기가 더 커야한다. (최근일 수록 버킷은 작아야 한다.)
• timestamp가 N을 벗어나면 bucket은 사라진다.

 

 

DGIM Algorithm은 

 

(A) timestamp는 1부터 N까지 기록하기 때문에 O(logN)의 비트만 있으면 된다.

• n개의 bit로 2^n의 수를 표현가능하므로 정수 n의 표현하고자 필요한 bit수는 log n이 됨)     

 

(B) 1의 개수를 저장하기 위해서는 O(log log N) 비트가 필요하다.

• 1의 개수는 2의 제곱수로 표현해야하는데, count값을 저장할 때 2^k가 아닌 k만 저장하면된다. 
• 예를 들어서 16을 저장하기 위해서는 4비트(2^4)가 필요한 것이 아니라 4만 저장하면 되므로 1비트만 필요로 한다. 

 

결국 하나의 버킷을 저장하기 위해서는 O(logN) + O(log log N) = O(logN)이 되며,

전체 버킷에서 1의 개수를 예측하기 위해서는 전체 버킷의 수를 곱해주면 된다. O(logN) * O(logN) = O(log^2N)

 

 

Updating Buckets

 

버킷을 업데이트하는 것은 stream 에 0이 들어오거나 1이 들어오는 2가지의 경우로 나뉘게 된다.

 

1) 0이 들어오는 경우

 

DGIM 알고리즘의 경우 새로운 bit가 0일 경우에는 어떠한 변화도 필요하지 않으므로 무시하면 된다.

(exponential window는 0, 1 모두 update해야함)

 

 

2) 1이 들어오는 경우

 

1이 들어오면 사이즈가 1인 bucket을 하나 만든다. 같은 level의 bucket이 3개가 되면, 가장 오래된(leftmost) 2개의 bucket을 합쳐 higher level로 올리고, 이러한 과정을 반복한다.

 

 

Error Bound

 

왜 DGIM method의 error rate이 50%일까? 증명해보도록 하자.

먼저 last bucket size(= unknown area)가 2^r 이라 하면, error는 그 절반인 2^(r-1)이다.

 

그리고 unknown area의 이전 bucket size를 다 더하면 1+2+4+ ... + 2^(r-1) = 2^r - 1 이 된다. (등비수열 이용) 우리는 bucket의 starting point를 무조건 1로 고려했으므로 1을 더해주면 2^r이라 할 수 있다

 

결국 error는 2^(r-1) / 2^r = 50%