DGIM(Don't Go Into the Mist) 알고리즘은 데이터 스트림에서 최근 시간 동안 발생한 1의 개수를 추정하는 알고리즘이다. 이 알고리즘은 스트림 데이터의 크기가 매우 크거나 무한할 때 유용하게 사용된다.
DGIM 알고리즘은 슬라이딩 윈도우 기반으로 동작한다. 윈도우는 고정된 크기를 가지며, 스트림 데이터가 윈도우 밖으로 나가면서 가장 오래된 데이터는 버려진다. 알고리즘은 윈도우 내의 1의 개수를 유지하면서 시간에 따라 지속적으로 업데이트한다.
DGIM 알고리즘은 세 가지 규칙을 사용하여 윈도우 내의 1의 개수를 추정한다:
- 윈도우 내에서 발생한 1의 개수를 이진 트리 형태로 유지한다.
- 각 노드는 이진 트리에서 가장 오래된 1의 타임스탬프를 저장한다.
- 인접한 두 노드의 크기는 2배로 증가한다.
알고리즘은 다음과 같이 동작한다:
- 데이터 스트림을 받아서 1인 데이터만을 처리하며, 시간에 따라 윈도우 내의 노드를 업데이트한다.
- 스트림 데이터가 윈도우의 크기보다 커지면, 가장 오래된 데이터를 제거하여 윈도우의 크기를 유지한다.
- 윈도우의 마지막 노드부터 시작하여 타임스탬프와 현재 시간 간의 차이를 계산하며, 윈도우 내의 1의 개수를 추정한다.
- 윈도우의 모든 노드를 검사한 후에는 각 노드가 표현하는 1의 개수를 더하여 최종 추정값을 계산한다.
DGIM 알고리즘은 정확한 결과를 제공하는 것은 아니지만, 매우 적은 메모리와 계산 비용으로 1의 개수를 근사적으로 추정할 수 있다. 따라서 대규모 데이터 스트림 처리나 실시간 데이터 분석 등에 유용하게 활용될 수 있다.
