Bloom filters

Filtering Data Stream

 

Filtering은 key list인 S가 주어지면, S에 어떤 stream의 튜플이 존재하는지 살피는 것으로 일종의 membership test에 해당한다. 가장 간단한 방법은 hash table에 S의 모든 key를 저장하면 되는데, 우리는 모든 key를 저장할 충분한 메모리를 가지고 있지 않다!

 

 

Bloom Filter

 

 

 

n의 길이를 가진 비트 배열과 k개의 해시 함수가 존재하며, 해시 함수들은 [0, n) 범위의 해시 값을 출력한다.

• 원소 추가 시, 추가하려는 원소에 대해서 k개의 해시 값을 계산한 후 각 해시 값을 비트 배열의 인덱스에 대응하는 비트를 1로 세팅한다
• 원소 검사 시, 검사하려는 원소에 대해서 k개의 해시 값을 계산한 다음, 각 해시 값을 비트 배열의 인덱스로 해서 대응하는 비트를 읽는다. k개의 비트가 모두 1인 경우 원소는 집합에 속한다고 판단하고, 그렇지 않은 경우 속하지 않는다고 판단한다.

 

 

Bloom Filter 특징

• Bloom Filter는 모든 key값을 저장하지 않고, 해시 함수를 통해 원소의 특징 값들만 뽑아서 비트 배열에 반영한다. 따라서 정확도는 떨어지게 되지만 메모리 사이즈를 매우 절약할 수 있다.
• False negative(존재하지 않는 원소를 존재한다고 판단할 가능성)는 없다. (bit array의 값이 0이면 무조건 not in S)
• False positive(존재하지 않는 원소를 존재한다고 판단할 가능성)가 존재할 수 있다.

 

---

 

여기는 저의 두서없는 설명이니 생략하시고, 후에 증명으로 보셔도 충분합니다.

사실, False positive만 존재하는 이유가 잘 이해되지 않았는데, 이러한 방식으로 이해해보려 하였다.

 

먼저 n개의 bit로 구성된 bit array B가 존재하고, 어떠한 element가 들어오면 hash 하여 그 해당 array의 index로 갔는데 그 값이 0이면 무조건 S에 속하지 않고, 1이면 속할 가능성이 높다고 판단한다는 것이다.

 

예를 들어, key값을 1을 넣어 해시하여 그 해쉬값이 50이 나올 수 있고, key값이 100 이어도 해쉬값이 50이 나올 수 있다고 가정해보자.

100을 넣어서 50이 나오면 bit array의 index 50에는 1로 세팅이 되어있을 거고, 후에 1이 들어와서 해쉬를 했더니 50이 나왔다면.... index 50에 1로 세팅된 것은 100때문이기 때문에 bloom fliter는 1은 이미 존재하는 element라고 리턴하게 되는데 이것이 false positive인 것이다. 

 

 

Throwing Dart

 

Q :  n개의 다트를 동일하게 나뉘어진 m개의 과녁에 던진다면, 하나의 과녁에 적어도 하나의 다트가 들어갈 확률은?

A : 다트가 1개, 과녁이 8개로 나뉘어져 있다면 하나의 과녁에 하나의 다트가 명중할 확률은 1/8일 것이다.

 

하지만 n과 m의 수가 매우 커진다면 확률에서 차이를 보인다.

 

 

Analysis

 

 

 

 

다트가 n개, 과녁이 m개인 상황에서, 하나의 과녁에 하나의 다트가 들어가지 않을 확률은 1 - 1/m

n개의 다트를 던지는 것은 독립적이므로, n개의 다트가 m개의 과녁에 들어가지 않을 확률은 (1 - 1/m)^n

 

식 (1 - 1/m)^n 을 (1 - 1 /m)^(m * n/m)으로 변형할 수 있으므로 e의 정의에 따라 1 - e^(-n/m) 이 된다.

 

그래서 전체에서 n개의 다트가 m개의 과녁에 들어가지 않을 확률을 빼주면 특정 과녁에 화살이 한 개라도 들어갈 확률이 되므로, 우리가 구하고자 하는 식은 1 - (1 - e^(-n/m))이 된다.

 

결국 위의 식을 bloom filter의 사례에 적용해보면

 

비트배열의 특정 비트가 임의의 한 원소가 필터를 거쳐 1로 바뀔 확률이  - (1 - e^(-n/m)) 이 되는 것이고,

이것이 false positive (error rate)의 확률이 되는 것이다. 

 

 

 

example

 

10^ 9개의 다트와 8*10^9 타깃이 있다고 가정하면,

Fraction of 1s in B = 1 - e ^(-1/8) = 0.1175 이다.

 

하지만 우리가 이전에 추정했던 1/8 = 0.125와는 차이가 크지 않다.

 

그렇다면 False positive 확률을 더 줄일 수 있는 방법은 없을까?

그 방법은 hash function의 개수 k를 조정하면 된다.

 

BloomFilter의 경우 시간 복잡도가 O(k*n)이기 때문에 k의 개수를 늘릴수록 수행 시간이 늘어난다.

(해시함수를 많이 쓸수록 m(bit array)은 고정되어있는데 그 안에 저장되는 비트수가 많아지므로 error가 증가)

 

하지만, 우리는 k개의 독립적인 해시 함수를 가지고 있고, 모든 k개의 해시 element x가 1의 버킷에 있는 경우에만 element x를 통과시키므로 false positive = (1 - e^(-kn/m))^k로 감소하게 된다.

 

그래서 적절한 k의 값은 m/n ln 2가 된다.

 

 

example에 적용해보면 적절한 k는 8*ln2 = 5.54 (대략 6)

error at k = 6 : (1-e^(-6/8))^6 = 0.0437

 

적절한 k개의 해시함수를 사용했더니 false positive가 감소한 것을 볼 수 있다.