블룸필터 - Bloom Filter

 

블룸필터란? 

블룸필터(Bloom Filter)는 특정 원소가 집합에 속하는지 검사하는 데 사용할 수 있는 확률형 자료구조다.

확률적 검색 필터로 우너하는 패턴이 무엇인지 정확하게 규정할 필요 없이 원하는 패턴을 설명하는 방식 

 

블룸필터는 프라이버시를 보호하면서 검색 패턴을 구현하기 위한 효율적인 방법을 제공함

SPV(Simplified Payment Verification)노드는 블록헤더만을 저장하여 거래의 유효성을 높이는 노드인데 
블룸필터를 사용해서 이웃노드들에게 특정 거래를 제공해달라고 요청하는 데 이 떄 노드는 검색중인 주소에 대해 정확히 밝힐 필요가 없음 

 

 

블룸필터 동작 방식

블룸필터는 m 비트 크기의 비트 배열구조를 가지고 k가지의 해시함수를 사용해서 입력된  원소에 대해 m가지의 값을 균등한 확률로 출력한다.

https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0

 

• 원소를 추가하는 경우 추가하려는 원소에 대해 k가지의 해시값을 계산한 뒤 해시값에 대응하는 비트를 1로 설정한다.
• 원소를 검사하는 경우 해당원소에 대해 k가지의 해시값을 계산한 다음 각 해시값에 대응 하는 비트값을 읽는다. 

 

블룸필터의 특징 1 - 거짓-긍정확률이 존재

블룸필터는 길이 N의 이진 배열(Binary array)와 1부터 N까지의 출력값을 갖는 J개의 해시함수를 가지고 있다고 하는데 이 N과 J를 조절함으로써 정확도와 정확도와 프라이버시 보호 수준을 조절할 수 있음

 

오탐지율이 존재하기 때문에 결정적(Deterministic) 결과 대신 부정확한 결과를 얻을 수 있음

 

False Negative(거짓-부정, 존재하지만 부정하는 것)은 존재하지 않는다고 보장할 수 있습니다.

하지만 False Positive(거짓-긍정, 존재하지 않지만 있다고 하는 것)가 존재할 수 있습니다. 

 

즉 특정 원소가 존재하지 않는다는 부정적인 답변을 받으면 이 원소는 확실하게 없다고 할 수 있음

 

 

블룸필터의 특징 2 - 제거 불능

있는지 없는지만을 보는 특성 때문에 삽입만 가능하고 제거가 안된다. 

 

 

 

블룸 필터 사용 예

블룸필터는 처리능력 대비 적은 메모리 공간을 필요로 하는 장점때문에 DB 이외에도 많은곳에서 사용

 

1. IP 주소 검색 및 차단 필터링

2. 문자열 맞춤법 교정
3. 가상화폐
4. 라우터
5. 크롬 브라우저
6. 빅데이터 환경

 

 

go로 구현하는 블룸필터 : 링크

 

 

참고

블룸필터 위키

코드스테이츠