블룸 필터는 약간의 오답을 적은 메모리 사용량과 맞바꿨다

항목 집합이 방대할 때 모든 키를 저장하는 것은 불가능하지만, 그래도 어떤 항목이 집합에 있는지는 알아야 한다. 블룸의 예시는 50만 단어 사전이었는데, 단어의 10%만이 값비싼 하이픈 연결 규칙을 사용했다. 합리적인 검사는 디스크 접근을 피하는 것이었지만, 사전은 사용 가능한 메모리에서 오류 없는 해싱을 하기에는 너무 컸다.

블룸 필터는 비트 배열과 여러 해시 함수로 이 문제를 해결한다. 항목을 추가하면 해당 위치의 비트를 설정하고, 검사는 그 비트들이 모두 설정되어 있는지 묻는다. 하나라도 0이면 그 항목은 확실히 없으므로 거짓 부정은 없다. 모두 설정되어 있으면 그 항목이 집합에 있을 수도 있고, 다른 항목들과 충돌했을 수도 있으며, 이때 거짓 긍정이 발생한다.

오류가 한쪽 방향으로만 발생하고 조정 가능하기 때문에, 구조는 작게 유지되면서도 대부분의 불필요한 디스크 읽기를 제거한다. 오류 없는 해시에 필요한 크기의 18%에 불과한 해시 영역으로 디스크 접근의 87%를 제거했고, 요소당 10비트 미만이면 약 1%의 거짓 긍정률을 얻는다.

비트 배열이 '아마'라고 말하게 하고, 실수로 '아니오'라고 말하지 않게 한다

비용이 추가 검사에 불과할 때는 거짓 긍정이 허용되지만, 거짓 '아니오'는 데이터를 잃게 한다.

몇 개의 해시 함수를 가진 비트 배열은 요소당 몇 비트로 집합 소속 여부를 저장한다.

실제 집합을 저장하지 않고도 대부분의 값비싼 디스크 또는 네트워크 조회를 제거한다.

'예'라고 말할 작은 가능성이 허용되지만 거짓 '아니오'는 허용되지 않는다면, 한쪽 방향의 오류를 의도적으로 받아들여라. 약간의 거짓 긍정을 허용하는 것이 방대한 집합을 메모리에 맞추는 유일한 방법인 경우가 많다.

블룸 필터는 값비싼 조회를 피하기 위해 데이터베이스, 캐시, 맞춤법 검사기, 네트워크 라우팅에 퍼졌으며, PostgreSQL과 Apache Cassandra부터 Chromium과 대규모 캐싱에 이르는 시스템에 등장한다. 공간을 위해 한쪽 방향의 오류를 받아들이는 이 근본적인 기법은 이제 컴퓨터 시스템 전반의 표준 기본 요소이다.