Count-Min Sketch
Count-Min Sketch은 스트리밍 데이터에서 키별 출현 횟수를 작은 다차원 카운터 배열로 추정한다 확률적 빈도 추정 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체...
| 분류 | 자료구조 · 확률적 빈도 추정 |
|---|---|
| 목적 | 스트리밍 데이터에서 키별 출현 횟수를 작은 다차원 카운터 배열로 추정한다 |
| 처리 방식 | d개의 해시 함수로 각 행의 카운터 하나씩을 증가시키고 조회 시 선택된 카운터들의 최솟값을 반환한다 |
| 복잡도·성능 | 업데이트·조회 O(d), 메모리 O(wd) |
| 필수 조건 | 카운터 크기와 해시 함수·오차 허용치를 정해야 하며 기본 구조는 음수 업데이트 없이 사용한다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
Count-Min Sketch은 스트리밍 데이터에서 키별 출현 횟수를 작은 다차원 카운터 배열로 추정한다 확률적 빈도 추정 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 d개의 해시 함수로 각 행의 카운터 하나씩을 증가시키고 조회 시 선택된 카운터들의 최솟값을 반환한다. 충돌은 추정 빈도를 증가시키는 방향으로 작용한다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 업데이트·조회 O(d), 메모리 O(wd) 올바르게 적용하려면 카운터 크기와 해시 함수·오차 허용치를 정해야 하며 기본 구조는 음수 업데이트 없이 사용한다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 빈도 추정·핫키 탐지·네트워크 통계에 활용한다. 전체 빈도 분포를 정확히 저장하는 해시맵보다 메모리가 작다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]