[CS246] Filtering Data Streams

Filtering with Hash Table, Bloom Filter

Application

Email spam filtering (이번 포스팅에서 자주 사용될 예시이다)

• 100만명의 user에 대하여 각 user마다 1000개의 good(trusted) 주소가 있다고 하자.
• good(trusted) mail은 NOT spam이다.

Publish-subscribe systems

• news 기사 데이터를 모으고 있다고 하자. (포털 사이트)
• 어떤 keyword에 대하여 관심이 있는 기사를 맞춰 제공할 수 있다.

Content filtering

• 보고싶은/보고싶지않은 컨텐츠를 필터링할 수 있다
• 광고시스템, 추천시스템 등

 

Bloom Filter: Algorithm

우리가 필터링하고 싶은 key의 집합을 $S$라 하자.

• 길이가 $n$인 bit array $B$를 $0$으로 초기화한다.
• $[0, n)$의 값을 갖는 해시함수 $h$를 고른다.
• $s \in S$에 대하여 $B[h(s)]=1$로 비트를 저장한다.
• (Runtime) 새로운 $a$에 대하여 $B[h(a)]=1$이면 $a$를 output한다.

Bloom Filter Algorithm (Stanford CS246)

 

False Positive: $1$ bucket으로 해싱되는 item이 실제로는 $S$에 있지 않을 수 있다.

NO False Negative: $0$ bucket으로 해싱되는 item은 절대로 $S$의 원소가 될 수 없다.

 

Bloom Filter: Analysis

false positive에 대하여 정확히 분석해보자.

얼마나 false positive가 존재할 수 있을까?

false positive를 더 줄일 수 있을까?

 

다트 던지기로 비유해보자. 다트는 item의 hash value이고, target은 bit bucket이 되겠다.

$m$개의 다트(item)과 $n$개의 target(길이가 $n$인 bit array)에 대하여, target이 최소 한개의 dart를 받을 확률은?

• 다트 한개를 놓칠 확률: $1-1/n$
• $m$개의 다트가 모두 missing: $(1-1/n)^m$
• 최소 한개의 다트가 target에 맞을 확률: $1 - (1-1/n)^m$

우리는 빅데이터에 대하여 다루고 있으므로 $n$이 매우 크다고 가정하면

\[ 1 - (1-1/n)^m \approx 1 - e^{-m/n} \]

이고 이것이 곧 false positive 확률이다.

 

예를 들어, 10억개의 이메일 주소들과 1GB의 bit array에 대하여 false positive rate (FPR)를 구해보자.

10억 = $10^9=m$이고 1GB = 8 bilion bits이므로 $n=8 \times 10^9$이다. FPR=$1-e^{-1/8}=0.1175$

 

Bloom Filter: Multiple Hash Functions

이전과 같이 $|S|=m$, $|B|=n$이고 추가로 $k$개의 독립적인 해시함수 $h_1, \dots, h_k$가 있다고 하자.

• 길이가 $n$인 bit array $B$를 $0$으로 초기화한다.
• $[0, n)$의 값을 갖는 $k$개의 해시함수 $h_1, \dots h_k$를 고른다.
• $s \in S$에 대하여 $k$개의 해시함수에 대하여 $B[h_i(s)]=1$로 비트를 저장한다.
• (Runtime) 새로운 $a$에 대하여 모든 해시함수에 대하여 $B[h_i(a)]=1$이면 $a$를 output한다.

전체 $km$개의 dart와 $n$개의 target으로 비유하면 $1$의 비율은 $1-e^{-km/n}$ 이다.

따라서 FPR = $(1-e^{-km/n})^k$ 이다.

 

Optimal $k$ (Stanford CS246)

참고로 수학적으로 optimal value of $k$는 $k^* = \cfrac{n}{m} \ln 2$ 이다.

그러나 $k$는 정수이므로 적당히 반올림해서 구한다. ($8 \ln 2 =5.54 \approx 6$)