블룸 필터 편집하기 (부분)

== 변형 및 확장 ==

=== 카운팅 블룸 필터 (Counting Bloom Filter) ===

기본 블룸 필터의 '''삭제 불가''' 문제를 해결하기 위해, 1998년 Li Fan 등이 제안한 변형이다. 비트(0/1) 대신 각 슬롯에 '''카운터(counter)'''를 저장한다.

{| class="wikitable" style="width:100%;"
|-
! 동작 !! 기본 블룸 필터 !! 카운팅 블룸 필터
|-
| 삽입 || 비트를 1로 설정 || 해당 카운터 +1
|-
| 삭제 || 불가능 || 해당 카운터 -1 (0 미만이면 무시)
|-
| 조회 || 비트가 모두 1인지 확인 || 카운터가 모두 0 초과인지 확인
|-
| 공간 || m bits || m × (카운터 비트 수), 보통 4~8배
|}

카운터 오버플로우(overflow) 문제가 있어 보통 4비트(최대 15까지 카운트) 카운터를 사용하며, 오버플로우 발생 시 더 이상 감소시키지 않는 처리가 필요하다.

=== 스케일러블 블룸 필터 (Scalable Bloom Filter) ===

기본 블룸 필터의 단점 중 하나는 '''미리 원소 수(n)를 알아야''' m과 k를 결정할 수 있다는 점이다. 스케일러블 블룸 필터는 여러 개의 블룸 필터를 계층적으로 쌓아, 현재 필터가 가득 차면 새 필터를 추가하는 방식으로 동적 확장을 지원한다.

* 각 단계마다 오탐률 목표를 tighter하게 설정 (예: 0.01, 0.001, 0.0001...)
* 전체 오탐률은 각 단계 오탐률의 합으로 bounded됨
* 공간 효율은 약간 감소하지만, 사전 크기 지정 불필요

=== 압축 블룸 필터 (Compressed Bloom Filter) ===

마이클 미첸마허(Michael Mitzenmacher)가 2002년 제안한 변형으로, 블룸 필터의 비트 배열을 [[산술 부호화(Arithmetic Coding)]]나 [[Golomb 부호화]]로 압축하여 네트워크 전송 효율을 높인다. 비트 배열이 희소(sparse)하거나 조밀(dense)할수록 압축률이 높아진다.

=== 블룸 필터의 집합 연산 ===

같은 m과 k를 공유하는 두 블룸 필터 A, B에 대해:

* '''합집합(Union)''': A OR B — 두 비트 배열을 비트 OR 연산 → <math>A ∪ B</math>를 나타내는 블룸 필터
* '''교집합(Intersection) 근사''': A AND B — 두 비트 배열을 비트 AND 연산 → <math>A ∩ B</math>를 근사

단, 교집합 연산은 오탐률이 증가하는 단점이 있다.

=== 스펙트럼 블룸 필터 (Spectral Bloom Filter) ===

원소의 존재 여부뿐만 아니라 '''빈도수(multiplicity)'''까지 추정할 수 있는 확장형이다. 카운팅 블룸 필터를 기반으로 하며, 각 원소의 최소 카운터 값을 빈도수 추정값으로 사용한다. [[스트리밍 알고리즘]]의 [[Count-Min Sketch]]와 개념적으로 유사하다.

=== 쿠쿠 필터 (Cuckoo Filter) ===

2014년 Fan et al.이 제안한 자료구조로, 블룸 필터의 직접적인 경쟁자다. 쿠쿠 해싱 기반으로 구현되며:

{| class="wikitable" style="text-align:center;"
|-
! 특성 !! 블룸 필터 !! 쿠쿠 필터
|-
| 삭제 지원 || 기본형 불가 || 가능
|-
| 조회 성능 || <math>O(k)</math> || <math>O(1)</math> (최적)
|-
| 공간 효율 || 우수 || 비슷하거나 약간 더 우수
|-
| 구현 복잡도 || 간단 || 복잡
|-
| 최대 부하율 || ~50% (1개 버킷) || ~98% (2개 버킷)
|}

낮은 오탐률(< 3%)에서는 쿠쿠 필터가 공간 효율적으로 블룸 필터를 능가한다고 알려져 있다.

=== XOR 필터 (XOR Filter) ===

2019년 Graf and Lemire가 제안한 최신 변형. 정적(static) 집합에 대해 구성되며, 쿼리 시 XOR 연산만 사용하여 매우 빠르고 메모리 효율적이다. 단, 집합이 변경되면 필터를 완전히 재구성해야 한다.

=== Ribbon 필터 ===

2021년 발표된 가장 최신 변형 중 하나. [[Random Linear Systems]]를 기반으로 하며 이론적으로 매우 높은 공간 효율을 보인다. [[RocksDB]] 같은 실용 시스템에 채택되기 시작하고 있다.

=== Learned Bloom Filter ===

2018년 Google Brain의 Tim Kraska 등이 제안한 머신러닝 기반 변형. 신경망 모델이 원소의 패턴을 학습하여 더 작은 공간으로 낮은 오탐률을 달성한다. 모델이 "아마도 있다"고 판단하는 원소에 대해서만 전통적인 블룸 필터로 재확인하는 하이브리드 구조다.