Count-Min Sketch

Count-Min Sketch

스트림 데이터의 원소 빈도를 근사적으로 추정하는 확률적 자료구조로, 해시 함수와 2차원 카운터 배열을 사용하여 작은 메모리로 빈도 쿼리를 지원하며 과대 추정 가능

목적: 빈도 추정, 스트림 처리, 메모리 효율, 상위 k개(Heavy Hitters)

특징: 확률적, 과대 추정만 가능, 과소 추정 없음, 작은 메모리, 해시 기반

구조: d×w 2차원 배열(d개 해시 함수, w개 카운터), 각 행은 독립적 해시 함수

동작

• •update(item): d개 해시로 각 행의 카운터 증가
• •query(item): d개 해시로 각 행의 카운터 조회 → 최소값 반환(과대 추정 최소화)

오차: ε-δ 보장, w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉, ε = 오차 한계, δ = 실패 확률

시간 복잡도: update·query 모두 O(d) - d는 상수

공간 복잡도: O(d × w) - 매우 작음

장점: 작은 메모리, 빠른 연산, 스트림 처리, 병렬화 가능

단점: 과대 추정 가능, 정확한 빈도 불가, 삭제 어려움(음수 카운트 문제)

적용사례: 네트워크 트래픽 분석, 상위 k개 쿼리(Heavy Hitters), 웹 분석, 스트림 처리, DDoS 감지

비교: Count-Min Sketch(과대추정/빠름) vs 해시 테이블(정확/큼) vs Count Sketch(양방향 오차)

연관: 확률적 자료구조, 스트림 처리, 해시 함수, Heavy Hitters