Count Min Sketch

대충 이해하기

강대명(charsyam@naver.com)

강대명 소개

• 현) 레몬트리 CTO

​

• 구) 위버스 데이터 엔지니어
• 구) 유데미 데이터 엔지니어
• 구) 카카오 백엔드 엔지니어
• 구) 네이버 백엔드 엔지니어
• 오픈소스 컨트리뷰터

Count를 확률적 자료구조

(Probabilistic Data Structures)

Count 를 위한 확률적 자료구조?

• 먼저 다음과 같은 예를 들어봅시다.
• 다음과 같이 IP들이 있는데, IP별로 개수를 세고 싶다.
• 10.0.0.1, 10.0.0.1, 10.0.0.2, 10.0.0.3, 10.0.0.3, 10.0.0.3, 10.0.0.4

​

IP가 100만개 정도 되는데

Count를 해야 한다면?

IP 개수에 따른 메모리 할당 양

• IP 개수가 늘어날 수록 메모리 사용량도 늘어난다.

IP는 특정 IP 들이 많을까?

모두 동일한 횟수로 접근할까?

TOP(K)의 Count가 정확해야할 때

Count Min Sketch 가 유리

근사한 Count 값을 구하는 것이 목적

계산 시간과 메모리를 적게 사용하면 좋겠다.

d = 몇 개의 hash 함수를 쓸 것인가?

w = 메모리 공간을 얼마나 쓸 것인가?

(어라, BloomFilter와 비슷하네?)

Count Min Sketch

• 할당되는 메모리는 w * d * 변수 크기 만큼 사용된다.

w: 사용하고자 하는 메모리 공간

d

hash는 서로 다른 hash를 사용

hash % w 값을 이용

(이것도 BloomFilter 랑 유사하네?)

다음과 같은 데이터셋이 있다고 가정한다.

​

1.1.1.1

2.2.2.2

1.1.1.1

3.3.3.3

1.1.1.1

최초

• 최초에는 모두 0으로 셋팅

Add : 1.1.1.1

• hash1(1.1.1.1) = 1
• hash2(1.1.1.1) = 5
• hash3(1.1.1.1) = 2
• hash4(1.1.1.1) = 1
• 나온 해시 값의 자리를 1 증가시킨다.

Add : 2.2.2.2

• hash1(2.2.2.2) = 2
• hash2(2.2.2.2) = 4
• hash3(2.2.2.2) = 4
• hash4(2.2.2.2) = 2
• 나온 해시 값의 자리를 1 증가시킨다.

Add : 1.1.1.1

• hash1(1.1.1.1) = 1
• hash2(1.1.1.1) = 5
• hash3(1.1.1.1) = 2
• hash4(1.1.1.1) = 1
• 나온 해시 값의 자리를 1 증가시킨다.

Add : 3.3.3.3

• hash1(3.3.3.3) = 1
• hash2(3.3.3.3) = 3
• hash3(3.3.3.3) = 5
• hash4(3.3.3.3) = 2
• 나온 해시 값의 자리를 1 증가시킨다.

Add : 1.1.1.1

• hash1(1.1.1.1) = 1
• hash2(1.1.1.1) = 5
• hash3(1.1.1.1) = 2
• hash4(1.1.1.1) = 1
• 나온 해시 값의 자리를 1 증가시킨다.

Count : 1.1.1.1

• hash1(1.1.1.1) = 1
• hash2(1.1.1.1) = 5
• hash3(1.1.1.1) = 2
• hash4(1.1.1.1) = 1

각 자리의 값을 정한다.

(hash1, 1) = 4, (hash2, 5) = 3, (hash3, 2) = 3, (hash4, 1) = 3

이때 4, 3, 3, 3 중에서 가장 작은 MIN 값은 3이므로 1.1.1.1의 개수는 3이 된다. 이래서 Count Min Sketch 이다.

Count : 3.3.3.3

• hash1(3.3.3.3) = 1
• hash2(3.3.3.3) = 3
• hash3(3.3.3.3) = 5
• hash4(3.3.3.3) = 2

(hash1, 1) = 4, (hash2, 3) = 1, (hash3, 2) = 1, (hash4, 1) = 2

이때 4, 1, 1, 2 중에서 가장 작은 MIN 값은 1이므로 3.3.3.3의 개수는 1이 된다.

BloomFilter 와 유사하게 Hash를 사용한다.

여러 hash 중에 가장 작은 값이 자기의 Count 값과

유사할 것이라는 점을 이용

w가 1000000이고 d 가 4라면

4 * 1000000 * 4 해서

16mb 정도로 메모리를 사용

16mb < 77.49MB

Count Min Sketch는 Hash의 충돌을 감안

고정된 크기에서 특정 값의 개수를

근사치로 구할 수 있다.

실제 값 <= 근사치 값

w와 d를 늘릴 수록 충돌이 줄어드므로

에러 값이 줄어든다.

근사값이라 운이 나쁘면 튀는 값이 나올 수도 있음.

여러 hash 값 들 중에 가장 적은 값이

해당 값에 가장 가까운 근사값

Reference

• 확률적 자료구조를 이용한 추정 - 빈도(Frequency) 추정을 위한 Count-Min Sketch
• https://d2.naver.com/helloworld/799782

​

감사합니다.