위키득계정 ↗
기술

블룸 필터

블룸 필터기술
영어
Bloom filter
목적
집합 포함 여부의 근사 검사
가능한 오류
없는 항목을 있다고 판단
설계 요소
예상 항목 수와 허용 오류율
블룸 필터는 항목이 집합에 들어 있는지를 작은 공간으로 검사하는 확률적 자료구조다. 정상적으로 항목을 추가하고 유지한 기본 필터는 없는 항목을 있다고 답할 수 있지만, 추가된 항목을 없다고 답하지는 않는다.

두 가지 답의 의미

검사 결과가 음성이면 해당 항목은 필터에 추가된 집합에 없다. 양성은 존재 가능성을 뜻하며 실제 존재를 확정하지 않는다. 따라서 필터를 정확한 집합과 같은 방식으로 해석하면 안 된다. 필터가 최신 상태로 갱신되지 않았다면 저장된 집합과 실제 시스템 상태 사이의 차이도 따로 고려해야 한다.

비싼 조회 앞에서 사용하기

예를 들어 보관 중인 파일 이름을 검사할 때 필터가 음성이면 원본 목록을 조회하는 일을 줄일 수 있다. 양성이면 원본 목록을 확인해 확정한다. 없는 파일을 있다고 확정해 처리하기보다 저렴한 사전 검사와 정확한 후속 검사를 연결하는 방식이다.

크기 선택

예상 항목 수와 허용할 오류율에 맞추어 공간을 잡는다. 같은 항목 수에서 더 낮은 오류율을 요구하면 일반적으로 더 많은 메모리가 필요하다. 고정된 필터에 예상보다 많은 항목을 넣으면 오류율이 커질 수 있으며, 확장 구현은 여러 하위 필터를 사용하므로 검사 비용도 살펴야 한다.

빈도 추정과의 구분

블룸 필터의 기본 질문은 항목의 존재 여부다. 항목이 몇 번 나타났는지를 추정하는 카운트 민 스케치와 목적이 다르다. 또한 오류율을 양성 결과 중 틀린 결과의 비율로 곧바로 해석해서는 안 된다. 그 비율은 실제로 없는 항목을 얼마나 자주 질의하는지에도 영향을 받는다.

관련 문서

집합 / 자료구조 / 해시 함수 / 확률 / 메모리 / 카운트 민 스케치 / 데이터베이스