-블룸 필터는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조

-블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능

-원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다

-집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능

-집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가

구조

• 블룸 필터는 _m_비트 크기의 비트 배열 구조를 가진다
• 블룸 필터에서는 k가지의 서로 다른 해시 함수를 사용한다
  • 각 해시 함수는 입력된 원소에 대해 m가지의 값을 균등한 확률로 출력해야 한다.
• 원소를 추가
  • 추가하려는 원소에 대해 k가지의 해시 값을 계산한 다음, 각 해시 값에 대응하는 비트를 1로 설정
• 원소를 검사
  • 해당 원소에 대해 k가지의 해시 값을 계산한 다음, 각 해시 값에 대응하는 비트값들을 읽는다
    • 모든 비드가 1인 경우 원소가 속한다고 판단
    • 그외에는 속하지 않는다고 판단

예제

이미지 출처 : https://en.wikipedia.org/wiki/Bloom_filter

• m=18, k=3
• 집합에 x, y, z를 추가
• w가 집합에 존재하는지 검사
  • w이 세 해시값 중 블룸필터 값이 0인 경우가 존재
  • w는 집합에 속하지 않는다고 판단 가능

참고

• https://en.wikipedia.org/wiki/Bloom_filter