블룸 필터
블룸 필터은 원소의 집합 포함 여부를 적은 메모리로 검사하되 거짓 양성을 허용하는 비트 기반 필터다 확률적 집합 자료구조 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계...
| 분류 | 자료구조 · 확률적 집합 자료구조 |
|---|---|
| 목적 | 원소의 집합 포함 여부를 적은 메모리로 검사하되 거짓 양성을 허용하는 비트 기반 필터다 |
| 처리 방식 | 원소를 여러 해시 함수로 비트 배열의 위치에 매핑하여 삽입 시 해당 비트를 1로 만들고 조회 시 모든 비트가 1인지 검사한다 |
| 복잡도·성능 | 삽입·검사 O(k) 해시 연산, 저장 m비트; 거짓 양성률은 m,n,k에 의존 |
| 필수 조건 | 해시 함수의 분포와 목표 거짓 양성률, 삽입 수의 상한이 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
블룸 필터은 원소의 집합 포함 여부를 적은 메모리로 검사하되 거짓 양성을 허용하는 비트 기반 필터다 확률적 집합 자료구조 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 원소를 여러 해시 함수로 비트 배열의 위치에 매핑하여 삽입 시 해당 비트를 1로 만들고 조회 시 모든 비트가 1인지 검사한다. 표준 구조에서는 거짓 음성이 없지만 삭제를 직접 수행하기 어렵다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 삽입·검사 O(k) 해시 연산, 저장 m비트; 거짓 양성률은 m,n,k에 의존 올바르게 적용하려면 해시 함수의 분포와 목표 거짓 양성률, 삽입 수의 상한이 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 데이터베이스·캐시·네트워크 필터에서 불필요한 실제 조회를 줄인다. 정밀한 집합 조회를 대체하지는 않는다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]