Bloom filtering

EXEM Knowledge Base

Jump to: navigation, 찾기

Bloom filter란 Burton Bloom이란 사람이 1970년의 Space/time trade-offs in hash coding with allowable errors라는 저작에서 처음으로 발표한 것이라고 하는데 이것은 간단히 말해 확률을 적용한 자료구조이다. 즉 어떤 집합에 A가 있는지, 없는지를 판단하는 자료구조인데 여기서 중요한 것은 A가 있느냐, 없느냐만 판단할 수 있으면 된다이지 A 자체를 원형대로 저장하고 있느냐는 아니다.

bloom filter는 두개의 컴포넌트로 구성되어 있다. 하나는 k 해쉬 펑션과 다른 하나는 주어진 길이의 bit 벡터이다. 우리는 bit vector의 길이와 key의 갯수에 맞는 해쉬펑션의 갯수를 선택할 수 있다. bloom filter의 모든 해쉬 펑션은 그들의 값의 범위와 bit vector의 길이와 맞아떨어진다. 예를 들어 vector가 200 bit로 되어 있으면 해쉬 펑션은 1에서 200까자의 수만을 반환하게 된다. 이것은 모든 가능한 값들이 균등하게 분배될 것을 보장한다.

Bloom filter로 키가 들어오면 우리는 이것을 k 해쉬 펑션중 하나를 통해 값을 얻어내고 이를 bit vector의 해당 위치를 찾아 이 vector를 설정한다. bit이 이미 설정되어 있다면 우리는 이것을 그냥 놔둔다. bloom filter에서 설정을 해제하는 메카니즘은 없다.

세개의 해쉬 펑션과 14개의 bit vector를 가지고 있는 예를 들어보자. 처음에 이 bit vector는 모두 비어있는 상태로 시작한다. 여기에 apple이라는 값이 들어와 해쉬 펑션을 수행하여 각각 3, 12, 11이라는 값을 얻었다고 가정하자. 그러면 아래와 같을 것이다.

OOOOOOOOOOOOOO --> OOXOOOOOOOXXOO

각 해쉬값 자리마다 설정이 되었다. 그리고 grape라는 값이 다시 들어와 각각 해쉬 값이 11,1,8을 얻게 되었다. 결과는 아래와 같다.

XOXOOOOXOOXXOO

11번째 자리는 이미 설정이 되어 있다. 즉 11 bit은 apple과 grape라는 두개의 정보를 모두 저장하고 있는 셈이 된다. 이렇게 중첩되는 것은 Bloom filter가 아주 심플하게 운영될 수 있다는 것을 의미하고 다른 한편으로는 기존의 key를 없애버릴 수 없다는 의미도 된다. apple이라는 key를 지우려면 이것을 처음부터 다시 시작하여 apple이라는 key를 집어넣지 않는 것 외에는 방법이 없다.

앞의 두가지 key는 bit vector에서 이들은 모두 bit vector내에 있고 각각의 특정 값을 설정할 수 있었으므로 이것은 valid하달 할 수 있다. 그러면 mango라는 키를 입력해 보자. 이것은 해쉬 펑션을 통해 8,3,12라는 값을 산출해 냈다. 일단 이것은 bit vector내에 모두 있기 때문에 valid라고 가정한다. 물론 mango는 valid한 값이 아니다. 왜냐 하면 모든 값들이 이미 설정된 값들이었기 때문이다. 이미 만들어진 필터와 값이 같은 것은 우연일뿐이다. 그러나 일단은 이것을 valid라고 한다.

bloom filter가 확률에 의한 자료구조라 하는 이유는 여기서 나온다. bloom filter는 false positive가 가능하기 때문이다. false positive란 없는데 있다라고 하는 오류의 일종이다. 예를 들면 병원에 갔는데 병이 없는데 병이 있다고 진단하는 오류인 셈이다. bloom filter는 bit vector의 길이와 필터에 저장된 키의 갯수로 false positive의 확률을 정한다. bit vector의 길이가 길 수록 이 확률은 적어진다. 그리고 해쉬 펑션을 덜 쓰면 키들을 분간해내기 어려울 것이고 만약 해쉬 펑션을 너무 많이 쓰면 쫑날 확률이 그만큼 커지게 된다.