[Ch 08. URL 단축기 설계] 블룸 필터는 무엇인가?

[yoon-chaejin]

블룸 필터는 무엇인가?

• 블룸 필터는 어떻게 동작하는가?
• 블룸 필터는 어떤 경우 활용할 수 있을까?

[yoon-chaejin]

블룸 필터는 어떻게 동작하는가?

• 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조
• 긍정 오류가 발생할 수 있지만, 부정 오류는 발생하지 않음
  • 긍정 오류 : 집합에 속하지 않는데 속한다고 함
  • 부정 오류 : 집합에 속하는데 속하지 않는다고 함
• 블룸 필터에 원소 추가
  • k개의 서로 다른 해시 함수를 사용해 계산한 원소의 해시 값을 비트에 표기
• 블룸 필터로 원소 검사
  • k개의 서로 다른 해시 함수를 사용해 계산한 원소의 해시 값을 표기한 비트 배열과 필터 간에 & 연산을 수행

[참고1]

[yoon-chaejin]

블룸 필터는 어떤 경우 활용할 수 있을까?

• 정확할 필요가 없는 대략적인 수치를 빨리 알고 싶을 때
• ex. 1년 치 사용자 별 이력을 뽑는데 페이코 사용자만 뽑아줘! 라는 요구사항을 처리할 때 1차적으로 데이터를 걸러내는 경우

[참고1 NHN Meetup BloomFilter는 언제 쓰나요?] [참고2 Cuckoo Filter]