Bloom Filter

Stream 형태의 무한한 데이터를 다루기 위한 알고리즘 중의 하나는 '필터링 알고리즘'이다. 스트림에서 X라는 속성을 가지는 데이터들을 걸러내는 알고리즘으로써 여러 메일들의 스트림을 입력받았을 때,  스팸메일을 걸러주는 프로그램등이 이 필터링 알고리즘을 적용한 예에 속한다. 

 

 

Filtering Data Streams

이전 포스팅의 예제와 마찬가지로 데이터 스트림의 각 원소는 Tuple(튜플, 순서쌍)의 형태로 입력이 된다. 

이때 필터링 알고리즘의 문제는 S라는 Key set이 들어왔을 때, 입력되는 튜플들의 스트림 중 S에 속하는 튜플들을 걸러내는 것이 된다.

이를 해결하기 위한 가장 명백한(Obvious) 방법은 해시 테이블(Hash Table)을 이용하는 것이다. 

 

 

해시 함수는 같은 키 값이 들어오면 무조건 같은 결과를 내놓는다는 특징을 가지고 있기 때문에, 어떤 튜플의 해시 함수 결과값이 S가 나타내는 특정 해쉬값들 중 하나와 동일하다면 굉장히 높은 확률로 그 튜플은 S에 속할 가능성이 있다는 것이다.

예를 들어 S에 속한 어떤 튜플A 의 해쉬값이 5라고 한다면, 데이터 스트림에서 추출한 튜플 A'의 해쉬값이 5가 나왔을 때, 

높은 확률로 A' = A이라는 것이다. 

 

 

하지만, 이 개념을 실제로 적용하기 위해서는 메모리의 측면을 생각해보아야 한다.

우리가 실제로 필터링 알고리즘을 적용하기 위해 사용하는 필터들은 그 단위가 100만개, 1000만개를 넘어가는 경우가 많기 때문에, 이 모든 필터들의 결과값을 내는 S 의 집합을 모두 메모리에 저장할 수가 없다. 

이런 문제를 해결하기 위해 등장한 것이 바로 Bloom Filter 이다. (메모리 절약을 위해)

 

 

Bloom Filter는 메모리의 각 비트를 해쉬 함수의 결과값으로 사용한다. 

 

Bloom Filter는 필터링에 필요한 모든 S값을 메모리에 저장하는 대신, 메모리를 절약하기 위한 조금 더 효율적인 방법을 사용한다. 

메모리를 비트들로 쪼개서 (예를 들어 1GB를 할당할 수 있으면, 비트의 수는 약 8*10^9개) 각 비트들의 값을 해쉬 함수의 결과값으로 사용한다는 것이다. 예를 들어서, 1GB의 메모리에서 얻을 수 있는 비트의 수는 약 80억개 정도가 된다. S의 개수가 10억개라면, S의 해쉬결과도 대략 10억개 정도가 나온다. (충돌의 경우가 생길 수 있으므로 대략이라고 표기하였다. )

이때, 이 10억개의 해쉬 결과를 번호를 매겨서 각각의 비트의 값에 1로 대응시켜주는 것이다. 

 

위의 그림을 보면 조금더 이해가 쉬울 것이다. 메모리를 일종의 Bit Array로 보고, 해쉬 함수의 결과를 이 비트배열의 인덱스로 삼아서 1로 바꾸어주는 것이다. 이렇게 되면, 비트배열에서 1인 비트는 해쉬 함수 S의 값을 포함하는 비트인 것이 된다.

이를 이용하면 새로운 튜플들을 필터링하는 것도 굉장히 쉬워진다. 

새로운 튜플 A가 들어왔을 때, 이를 해싱해서 그 값을 인덱스로 사용하여 비트 어레이(사실은 메모리)에 접근하고, 그 값이 1이면 S에 속하는 것이고, 0이면 속하지 않는 것으로 판단하면 되는 것이다. 

 

 

False Negative, False Positive

false negative = 버킷에 들어가야 하는데, 들어가지 못하는 경우

false positive = 버킷에 들어가면 안되는데, 들어오는 경우

 

Bloom Filter의 정확도를 구하기 위해 false negative, false positive의 확률을 구하는 것이 매우 중요하다.

먼저 False Negative를 살펴보면, 이는 그냥 0이다. 

왜냐하면 같은 속성을 가지고 있는 값들을 해싱하면 무조건 같은 값들이 나오기 때문에, 어떤 값이 S에 속하는데 그 것을 해싱한 결과가 비트 어레이에 속하지 않을 수는 없기 때문이다. (Hash Function의 성질 때문에 증명이 가능한 것이다.)

 

False Positive의 경우 조금은 확률론적으로 접근할 필요성이 있다.

 

 

Throwing Darts

 

m개의 다트를 n개의 과녁에 던지는 다트/과녁 모델을 생각해보자.

이때 우리가 구하고자 하는 것은 하나의 과녁에 적어도 하나의 다트가 명중할 확률이 얼마나 될까? 를 예측하는 것이다.

직관적으로 보았을 때, 다트가 1개이고, 과녁이 8개라면(다트가 빗나가는 경우는 없다고 가정했을 때), 1개의 과녁에 다트가 명중할 확률은 1/8이다. 그러나 다트의 개수와 과녁의 개수가 굉장히 큰 숫자일때는 차이를 보인다.

 

Proof.

다트가 y개, 과녁이 x개라고 했을 때, 하나의 과녁에 하나의 다트가 명중하지 못할 확률은 (1-1/x) 일 것이다. 

각 다트를 던지는 사건은 독립이므로, 따라서 y개의 다트가 특정 과녁에 하나도 명중하지 못할 확률은 (1-1/x)^y가 될 것이다.

이때, 위 식을 (1-1/x)^(x * y/x) 로 변형할 수 있고, e의 정의에 따라서  e^(-y/x)로 근사할 수 있다.

 

따라서, 특정 과녁에 y개의 화살이 하나도 명중하지 못할 확률은 e^(-y/x)라는 것이다. 이를 조금만 바꾸어 생각해보면

특정 과녁에 화살이 하나라도 명중할 확률은 1-e^(-y/x)인 것이다.

 

 

Application

이 다트/과녁 모델을 Bloom Filter 모델에 적용해 보자.

x = # of darts (S집합의 원소의 개수 -> 필터링되어서 비트에 1을 나타내야 하는 원소들의 개수)

y = # of targets (비트의 개수 -> 메모리의 용량이 1GB라면 80억개가 된다.)

 

위의 식을 적용하면, 특정 비트에 x개의 비트가 하나라도 적중하지 못할 확률은 1-e^(-y/x)이다. 즉, 비트 하나가 새롭게 들어온 인풋의 필터링에 의해 1로 바뀔 확률이 위와 같다는 것이다.  이는 결국 Probability of False Positive, 즉 S에 속해있지 않는 원소가 Bloom Filter를 거쳐서 특정 비트 값을 1로 바꾸는 확률과 같다고도 볼 수 있다.

 

따라서 어떤 임의의 한 원소가 필터를 거쳐서 특정 비트를 1로 바꿀 확률은 1-e^(-y/x) 이고, 이는 false negative 의 확률이 된다.

그렇다면 이 False Negative의 확률을 줄일 수 있는 방법은 없을까?

 

바로 Hash Function의 개수 k를 조정하면 된다.

Bloom Filter의 시간복잡도가 O(km)이기 때문에 k의 개수에 따라 수행 시간이 늘어나기는 하지만, 독립적인 여러 개의 해시 함수를 사용하여 해쉬함수를 통과한 값이 모두 1에 걸릴때만 S에 속하는 것으로 인정한다면 확률은 (1-e^(-km/n))^k)로 줄어들게 된다.