카운트-민 스케치 (count-min sketch)
쉽게 풀면
수억 개의 서로 다른 항목이 몇 번씩 나왔는지를 모두 세려면 메모리가 감당이 안 됩니다. 이 자료구조는 여러 개의 해시함수로 각 항목을 작은 카운터 배열의 여러 칸에 매핑해 두고, 조회할 때는 그 칸들 중 가장 작은 값을 답으로 내놓습니다. 충돌 때문에 값이 부풀 수는 있어도 모자라지는 않으므로, 오차의 방향이 한쪽으로 고정됩니다.
왜 중요한가
네트워크 트래픽 모니터링이나 실시간 로그 분석처럼 데이터가 흘러가며 다시 볼 수 없는 스트림 환경에서 빈도 집계를 가능하게 합니다. 메모리 사용량을 원하는 오차 한계에 맞춰 미리 계산할 수 있고, 여러 서버에서 만든 스케치를 그냥 더해서 합칠 수 있다는 점도 분산 환경에서 큰 장점입니다. 자주 등장하는 항목 찾기의 표준 도구입니다.
논문에서는 이렇게 쓰입니다
메모리를 크게 아끼면서도 가장 많이 나온 항목들은 빠짐없이 찾아냈다는 결과입니다.
조금 더 깊게 보면
폭 w, 깊이 d의 2차원 카운터 배열과 d개의 서로 독립인 해시함수를 씁니다. 갱신 시에는 각 행에서 해당 해시값 위치의 카운터를 증가시키고, 조회 시에는 d개 값의 최솟값을 답으로 삼습니다. w를 e/ε, d를 ln(1/δ)로 잡으면 오차가 전체 빈도 합의 ε배를 넘을 확률이 δ 이하라는 보장이 성립합니다. 여러 스케치를 원소별로 더하면 합쳐진 스트림의 스케치가 되는 성질이 분산 집계를 쉽게 만듭니다.
주의할 점
블룸 필터는 원소의 존재 여부만 판정하는 반면 이 자료구조는 등장 횟수를 근사한다는 점이 다릅니다. 추정값이 실제보다 작아지지는 않지만 커질 수는 있으므로, 드물게 등장하는 항목의 상대 오차는 매우 커질 수 있습니다.