What is Bloom filter

블룸 필터는 확률적으로 원소가 집합에 포함되는지 여부를 검사하는데 사용되는 자료구조이다. 블룸 필터에 어떤 원소가 집합에 속한다고 판단된 경우 실제로 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다. 블룸 필터는 m비트 크기의 비트 배열 구조와 k개의 서로 다른 해시 함수를 사용한다. 각 해시 함수는 입력된 원소에 대해 m가지의 값을 균등한 확률로 출력해야 한다.

Pros

• 공간 효율적
  • 다른 데이터 구조에 비해 매우 적은 메모리를 필요로 하므로 메모리가 제한된 시나리오에 이상적
• 빠른 속도
  • 집합의 크기와 관계 없이 O(k)시간 내에 집합 구성 여부 테스트가 가능
• 구현 용이성
  • 고급 데이터 구조에 대한 많은 지식이 필요로 하지 않음
• 다용도
  • 캐싱, 네트워크 라우팅 및 스팸 필터링과 같은 광범위한 응용 프로그램에서 사용 가능

Cons

• false positive
  • 잘못된 긍정값을 반환할 가능성이 작게 존재함
• 요소 삭제 불가
  • counting bloom filter로 해결할 수 있지만 버킷의 arithmetic overflow 문제를 해결하기 위해 버킷의 크기나 개수가 충분히 커야 함
• 요소 카운팅 불가
• 해시 함수 요구 사항
  • 독립적이고 균일하게 분포된 해시 함수 집합을 필요로 함
• 오탐률 증가
  • 요소를 추가해도 실패하는 경우는 없지만 오탐률이 증가하기 때문에 오탐률을 줄이려면 비트 배열을 추가하거나 블룸 필터를 다시 생성해야 함