확률적 자료구조를 이용한 추정 - 빈도(Frequency) 추정을 위한 Count-Min Sketch

Count-Min Sketch는 HashMap과 같은 정확한 빈도 계산 방식이 유일한 원소 개수에 비례하는 메모리 공간을 요구하는 반면, 더 적은 메모리 공간으로도 빈도 추정이 가능한 확률적 자료구조입니다. 2003년 G.

Cormode와 S. Muthukrishnan이 발표했으며, 메모리 공간과 정확도는 반비례 관계입니다.

전체 원소 중 극히 일부만 빈도 값이 큰 분포에 적합하며, 네이버 IP 주소의 국가별 빈도 실시간 추정 등에 활용될 수 있습니다. 이 글에서는 Count-Min Sketch의 기본 원리와 동작 과정을 간략하게 설명하며, 열의 크기가 w이고 행의 크기가 d인 이차원 배열과 d개의 독립적인 해시 함수를 사용하는 구조를 소개합니다.

해시 충돌로 인해 근삿값 오차가 발생할 수 있음을 시사합니다.