DGIM

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

문제 상황

0과 1로만 이루어져 있는 bit들의 stream이 입력으로 들어오는 상황에서 최근 들어온 k개의 bit 중 1의 개수를 구해야 하는 상황이 있다고 합시다. 가장 쉽게 생각할 수 있는 방법은 최근 k개의 bit들을 저장해서 개수를 세는 방법입니다. 새로운 bit가 들어오면 가장 예전의 bit를 버린다면 스트림으로 들어오는 입력에서 1의 개수를 셀 수 있을 것입니다. 자료구조 queue를 사용한다면 어렵지 않은 해결책입니다.

하지만, 저장해야 할 bit 용량이 너무 커서 메모리에 담을 수 없다면 어떻게 해야 할까요? 최근 k개의 bit에서 1 bit의 합을 기록하는 방법도 있을 것입니다. 그런데 새로운 bit가 들어왔을 때 버리는 가장 오래된 bit가 0인지, 1인지 확인하는 방법이 없다는 단점이 있습니다.

하나의 가정

비트 스트림에 들어오는 1과 0의 비율이 일정하다는 가정을 해봅시다. 비율이 일정하다면 다음의 식을 통해 최근 k개의 1의 개수를 계산할 수 있습니다.

(k 비트 중 1의 개수) = k * (지금까지 1의 개수) / (스트림의 전체 길이)

만약 비트 스트림에 들어오는 1과 0의 비율이 일정하지 않다면 이 식은 사용할 수 없습니다.

이럴 때, 다음의 방법을 생각할 수 있습니다.

지수적으로 증가하는 windows

입력으로 들어오는 비트 스트림을 크기가 지수적으로 증가하는 영역에 나누어 각 영역의 요약 정보를 저장합니다. 이에 대한 그림은 아래와 같습니다.

이 방법은 같은 색깔의 영역은 최대 2개까지만 존재할 수 있다는 규칙을 따릅니다. 그리고 각 영역에는 1의 개수를 저장합니다.

위 상황에서 새로운 비트가 들어오면 비트 1개의 영역(위 그림에서는 파란색)을 새로 생성하고 영역의 1의 개수를 저장합니다. 하지만 여기서는 1개의 영역이 3개가 되므로 규칙을 만족하지 않게 됩니다. 그래서 이전에 있던 2개의 영역을 비트 2개의 영역(초록색)으로 합친다. 이 과정은 규칙을 만족할 때까지 연쇄적으로 일어납니다. 따라서 0이라는 새로운 비트가 들어오면 아래의 그림과 같이 됩니다.

여기서 k = 30일 때, 1의 개수를 세려면, k의 범위 안에 완전히 존재하는 영역에 기록된 1의 개수의 합산 결과와 잘린 영역에서 1의 개수를 추측해 더합니다. 잘린 영역에서 1의 개수를 추측하는 방법은 여러 방법이 있지만 (영역에 담긴 1의 개수) * (k에 포함된 잘린 영역의 비트 수) / (영역의 크기)로 추측할 수 있습니다. 그러면 아래의 그림처럼 5 + 4 + 2 + 2 한 값에, 7 / 16 * 7 \(\approx\) 3을 더해 1의 비트 수가 16이라 추측할 수 있습니다.

이 방법은 error가 bound 되지 않는다는 단점을 지니고 있습니다. 만약 1이 unknown 영역에만 존재한다면, (예측한 1의 개수) / (실제 1의 개수) = 3 / 0으로 bound 되지 않습니다.

DGIM(Datar-Gionis-Indyk-Motwani) 알고리즘

Bound 되지 않는 에러를 해결하기 위해 나온 알고리즘이 바로 dgim 알고리즘입니다. DGIM 알고리즘은 지금까지 위에서 설명한 지수적으로 증가하는 window와 비슷합니다. 차이점은 영역을 설정하는 방법입니다. DGIM 알고리즘에서 영역은 1의 수를 지수적으로 키워가며 영역을 만듭니다. 즉 1이 존재하는 곳에서만 영역을 생성합니다. 이렇게 생성하면 0만 있음에도 영역을 만들고 저장하는 일이 없어 에러가 bound 되지 않는 상황이 발생하지 않습니다. DGIM 알고리즘에 따라 영역을 만들면 아래의 그림과 같습니다.

이전에는 1의 개수를 영역마다 저장했었습니다. 하지만 DGIM 알고리즘은 1의 개수를 기준으로 영역을 만들기 때문에 영역 안에 1의 개수가 2의 거듭제곱 수만큼 존재한다는 것은 확실합니다. 따라서 영역에 저장하는 값은 다음과 같습니다.

• 영역의 시작 timestamp
• 영역의 끝 timestamp
• 영역 크기

만약 오래된 영역이 k의 영역을 완전히 벗어나면, 그 영역은 메모리에서 지웁니다. 1의 개수를 구하는 방법은 전과 동일하게 진행합니다.

이 알고리즘을 사용하면 에러가 50%를 넘지 않습니다. 한 번 살펴봅시다.

k의 범위에 걸친 영역의 크기를 \(2^r\)이라고 합시다. 위의 그림으로 보면 r = 3인 상황인 겁니다. 이 영역에 포함된 1들 중에서 절반이 k의 범위 안에 있다고 한다면, 최대 에러는 \(2^{r - 1}\)입니다. \(2^r\) 보다 작은 크기의 영역들은 최소 1개 이상은 존재하므로 k에 완전히 포함된 영역의 1 비트의 합은 \(2^r - 1\) 입니다. 따라서 에러는 50%를 넘지 않게 됩니다.