Bloom Filters

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

문제 상황

(key, value)의 tuple로 이루어진 스트림이 있다고 합시다. 그러면, key 값들이 담긴 집합 S가 있을 때, 스트림 내의 임의의 튜플이 집합 S에 존재하는지 확인하려면 어떻게 해야 할까요?

가장 쉽게 생각할 수 있는 방법은 집합 S를 hash table에 모두 저장하는 방법입니다. 하지만 스트림으로 들어오는 튜플들의 수가 너무 많다면, 그 많은 튜플들을 하나씩 다 S에 탐색하는데 시간이 오래 걸릴 것입니다.

비트 배열을 사용한 필터링

비트 배열을 사용해 필터링을 하는 방법이 있습니다. 필터링을 해서 집합 S에 확실히 없다고 판단되면 검색을 진행하지 않고, 있을지도 모른다고 판단이 되면 검색을 진행시킬 수 있습니다. 모든 튜플이 아닌 일부의 튜플들만이 검색을 진행할 수 있으므로 시간이 적게 걸릴 것입니다.

먼저 크기가 n인 비트 배열을 만들고, 값들은 모두 0으로 초기화합니다. 그리고 집합 S의 원소들이 입력으로 들어갈 해시 함수를 선정합니다. 해시 함수의 출력 범위는 비트 배열의 인덱스 범위와 동일([0, n))해야 합니다. 선정한 해시 함수에 집합 S의 원소들을 넣어 나온 출력 값을 인덱스로 삼아, 비트 배열의 해당 인덱스 값을 1로 변경합니다.

스트림에 있는 임의의 튜플 a = (k, v)가 필터의 입력으로 들어오면 k의 해시 값을 얻고, 해시 값을 인덱스로 해서 비트 배열을 조회할 때 그 위치의 값이 1일 때만 필터를 통과하게 할 수 있습니다.

 

이 방법은 false positive는 가능하나 false negative는 없습니다. 다시 말하면, 집합 S에 실제로 없지만 있을지도 모른다고 판단할 수는 있지만 집합 S에 실제로 존재하는 것을 없다고 판단하지 않는다는 것입니다. False positive가 가능한 이유는 해시 충돌 때문입니다.

False Positive일 확률

False positive 확률은 비트 배열에서 1의 비율을 구하는 것과 같고, 이는 비트 배열의 특정 비트가 1일 확률을 구하는 것과 같습니다.

집합 S의 하나의 튜플의 key를 해시한 결과가 특정 비트의 인덱스가 나올 확률은 1 / n입니다. 그렇다면 특정 비트의 인덱스가 나오지 않을 확률은 1 - 1 / n 이 되고 집합 모든 집합의 튜플들의 key로 해싱할 때 특정 비트의 인덱스가 나오지 않을 확률은 \(\left( 1 - {1 \over n} \right)^m \)입니다. 따라서 특정 비트가 1일 확률은 \(1 - \left( 1 - {1 \over n} \right)^m\)입니다. 이는 약간의 변형을 통해 아래와 같이 표현할 수 있습니다.

$$ 1 - \left( 1 - {1 \over n} \right)^m = 1 - \left( 1 - {1 \over n} \right)^{n {m \over n}} \approx 1 - e^{-{m \over n}} $$

만약 집합 S의 크기가 1,000,000이고, 비트 배열의 길이가 100,000,000이면 false positive의 확률은 약 0.009950167입니다.

Bloom Filter

Bloom filter는 위의 방법에서 해시 함수를 여러 개 사용하자는 아이디어만 추가하면 됩니다. 비트 배열을 초기화할 때, k개의 해시 함수를 통과해서 나온 해시 값들을 인덱스로 삼아, 각 인덱스의 값을 1로 바꾸면 됩니다.

스트림을 통해 들어온 튜플도 key 값을 k개의 해시 함수를 거쳐 비트 배열에 조회하고, 모든 인덱스의 값이 1이면 필터를 통과하고, 하나라도 0이 있다면 통과하지 않습니다.

 

Bloom filter 또한 false negative의 경우가 나오지 않으며, 스트림의 크기에 상관없이, 메모리를 제한적으로 사용합니다. 따라서 오래 걸리는 연산 이전에 사전 처리하는 용도로 적절합니다.

False Positive 확률

해시 함수를 k개 사용하기 때문에 이전의 식을 그대로 사용할 수 없습니다.

비트 배열에서 1의 비율은 \(1 - e^{-{km \over n}}\)입니다. 그리고, 모두 1일 때만 필터를 통과하기 때문에 fasle positive 확률은 \(\left( 1 - e^{-{km \over n}} \right)^k\)입니다. 집합의 크기가 10억이고, 비트 배열의 크기가 80억 일 때, 그래프를 그려보면 아래와 같습니다.

이 그래프를 통해 최적의 해시 함수의 개수를 파악할 수 있습니다. 위의 그래프를 미분했을 때 기울기가 0인 지점이 바로 최적의 개수입니다. 위 그래프인 경우 해시 함수를 4 ~ 6개 사용하는 것이 적절해 보입니다.