카운트-민 스케치 (Count-Min Sketch)

블룸 필터가 "있냐 없냐"에 답한다면, 카운트-민 스케치는 "이 항목이 지금까지 몇 번 나왔나?"에 아주 작은 고정 메모리로 답하는 확률적 자료구조다. 항목을 하나도 저장하지 않고, 2차원 카운터 표(깊이 d × 폭 w)와 d개의 해시 함수만 쓴다. 추정값은 항상 실제값 이상(과대추정)이며 절대 과소추정하지 않는다 — 그래서 이름이 Count-Min: 여러 칸 중 최솟값을 답으로 고른다.

직접 해보기 — 항목을 여러 번 넣고, 빈도를 물어보자

표 크기: 깊이 d = 4 · 폭 w = 10 (총 40칸)

항목을 넣으면 각 행에서 해시가 가리키는 칸 1칸씩(총 d칸)이 +1 됩니다.

실제 넣은 횟수 (스케치는 저장 안 하지만 비교용):

아직 없음

초록 = 방금 +1 한 칸 · 주황 = 조회가 확인한 d개 칸 · 파랑 = 그중 최솟값 = 최종 추정값

어떻게 동작할까

넣기 — update(x, c=1)

각 행 i(0..d-1)마다 서로 다른 해시 hᵢ(x) mod w로 열을 구한다.
그 d개 칸에 각각 c를 더한다.
스트림에서 항목이 지나갈 때마다 이 연산만 반복 → O(d).

조회 — query(x)

같은 방식으로 d개 칸을 찾는다.
d개 값 중 최솟값을 답으로 낸다.
다른 항목과 해시 충돌이 난 칸은 부풀려져 있으니, 가장 덜 오염된 칸(=최솟값)이 진실에 가장 가깝다.

왜 항상 과대추정? 내가 실제로 넣은 만큼은 무조건 더해져 있고, 거기에 남의 충돌분이 얹히기만 한다(카운터는 음수가 안 됨). 그래서 추정값 ≥ 실제값이 항상 성립하고, d개 중 최솟값을 골라 이 부풀림을 최대한 줄인다.

비유: 4명의 목격자에게 "그 사람 몇 번 지나갔어요?"라고 묻는다. 다들 헷갈려서 실제보다 많게 말하지만(닮은 사람과 혼동), 아무도 적게는 말하지 않는다. 가장 낮게 말한 사람의 답이 제일 믿을 만하다.

오차 계산기 — 표 크기와 스트림 길이를 조절해 보자

폭 w (= ⌈e / ε⌉ 로 오차 ε 결정) 2,719

깊이 d (= ⌈ln(1/δ)⌉ 로 실패 확률 δ 결정) 5

스트림 전체 개수 N (모든 +1의 합) 1,000,000

오차 한계 ε·N = (e/w)·N

—

이 한계를 넘을 확률 δ = e^−d

—

스케치 메모리 (w·d·4바이트)

—

슬라이더를 움직이면 값이 실시간으로 바뀝니다.

보장: 확률 1−δ 이상으로 추정값 ≤ 실제값 + ε·N. 폭 w를 키우면 충돌이 줄어 오차 ε가 작아지고, 깊이 d를 키우면 "운 나쁘게 모든 행이 다 오염될" 확률 δ가 지수적으로 작아진다. 핵심은 메모리가 스트림 길이 N·서로 다른 항목 수와 무관하게 w·d로 고정이라는 점.

상위 빈발 항목(heavy hitters) — 추정이 얼마나 정확할까

위 데모에 넣은 항목들의 실제 빈도와 스케치 추정을 나란히 비교한다. 작은 표(d=4, w=10)라 충돌이 잦아 과대추정이 눈에 띈다 — 실제 서비스는 w를 수천으로 키운다.

아직 넣은 항목이 없습니다.

딕셔너리 카운터 · 블룸 필터 · HyperLogLog와 비교

질문	Count-Min Sketch	dict 카운터	Bloom / HLL
답하는 것	항목별 빈도(횟수)	항목별 정확한 빈도	있냐없냐 / 고유개수
메모리	고정 `w·d`	고유 항목 수에 비례	고정/작음
오차	과대추정 (≤ +ε·N)	없음	확률적
과소추정	절대 없음	없음	—
update / query	`O(d)`	`O(1)`	`O(k)`
삭제·감소	불가 (음수 X) — Count-Mean-Min·CU 변형 존재	가능	보통 불가

희소한 항목일수록 위험: 실제로 2번 나온 항목이 큰 항목들과 충돌하면 추정이 크게 부풀 수 있다. 그래서 CMS는 "소수의 초대형 빈발 항목을 찾는" 용도에 강하고, 꼬리(rare item)의 정확한 값에는 약하다.

파이썬으로 구현

import hashlib, math

class CountMinSketch:
    def __init__(self, epsilon=0.001, delta=0.01):
        self.w = math.ceil(math.e / epsilon)      # 폭: 오차 ε
        self.d = math.ceil(math.log(1 / delta))    # 깊이: 실패확률 δ
        self.table = [[0] * self.w for _ in range(self.d)]

    def _cols(self, key):
        h = hashlib.sha256(str(key).encode()).digest()
        for i in range(self.d):                     # 행마다 다른 해시
            hi = int.from_bytes(h[i*4:i*4+4], "big")
            yield i, hi % self.w

    def update(self, key, c=1):
        for i, j in self._cols(key):
            self.table[i][j] += c

    def query(self, key):
        return min(self.table[i][j] for i, j in self._cols(key))

# cms = CountMinSketch(epsilon=1e-4, delta=1e-3)   # 약 108KB
# for word in stream: cms.update(word)
# cms.query("apple")   # 실제값 이상, 대개 근접

합치기(merge): 두 스케치를 칸끼리 그냥 더하면 두 스트림을 합친 스케치가 된다. 덕분에 여러 서버에서 따로 집계한 뒤 한곳에서 합산하기 좋다(분산 집계).

실제로 어디에 쓰일까

네트워크 모니터링 — 초당 수백만 패킷 스트림에서 트래픽 상위 IP·플로우(heavy hitter), DDoS·엘리펀트 플로우 탐지.
검색·추천 — 인기 검색어·트렌딩 항목의 대략적 빈도를 실시간 집계.
데이터베이스 (Redis, 스트림 처리 Spark·Flink) — 근사 빈도 집계 연산자로 내장.
NLP — 대규모 코퍼스에서 n-gram 빈도를 메모리 한도 안에서 추정.
광고·과금 — 노출/클릭 카운트의 저비용 근사, 이상 급증 감지.

사촌들: 최솟값 대신 편향 보정을 하는 Count-Mean-Min, 넣을 때 최솟값 칸만 올려 과대추정을 줄이는 Conservative Update(CU Sketch), 양수·음수를 모두 다루는 Count Sketch.