본문으로 건너뛰기

1. Bloom Filter란?​

  • 블룸 필터(Bloom Filter)는 원소가 집합에 속하는지 여부를 검사하는 확률적 자료 구조입니다.
  • 개발: 1970년 Burton Howard Bloom에 의해 고안
  • 용도: 빠른 멤버십 테스트 (원소가 집합에 있는지 확인)
  • 특징: 공간 효율적이지만 확률적 오류 발생 가능

1.1 핵심 특성​

블룸 필터의 가장 중요한 특성은 오류의 비대칭성입니다:

판단 결과실제 상황오류 발생 가능성
"속한다"실제로 속하지 않음✅ 긍정 오류(False Positive) 가능
"속하지 않는다"실제로 속함❌ 부정 오류(False Negative) 절대 발생 안 함
긍정 오류 (False Positive)

블룸 필터가 "원소가 집합에 속한다"고 판단했더라도, 실제로는 속하지 않을 수 있습니다.

하지만 "속하지 않는다"고 판단하면 100% 확실하게 속하지 않습니다.

1.2 제약사항​

  • 추가만 가능: 집합에 원소를 추가하는 것은 가능
  • 삭제 불가능: 집합에서 원소를 삭제하는 것은 불가능
  • 오류 확률 증가: 원소 수가 증가할수록 긍정 오류 발생 확률 증가

2. 구조​

2.1 기본 구성 요소​

블룸 필터는 두 가지 핵심 요소로 구성됩니다:

1. 비트 배열

m비트 크기의 비트 배열

초기 상태: [0, 0, 0, 0, 0, 0, 0, 0, ...]
           └────────── m개 ──────────┘

2. 해시 함수

k개의 서로 다른 해시 함수

h₁(x), h₂(x), h₃(x), ..., hₖ(x)

각 해시 함수는:
- 입력: 원소
- 출력: 0 ~ m-1 범위의 값 (균등 분포)

2.2 예시​

블룸 필터 설정: m = 18비트, k = 3개 해시 함수

비트 배열:
[0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0]
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17

원소 x, y, z가 추가된 상태
해시 함수 요구사항

각 해시 함수는 m가지의 값을 균등한 확률로 출력해야 합니다. 이는 비트 배열 전체를 골고루 사용하기 위함입니다.

3. 연산​

3.1 원소 추가 (Add)​

원소를 추가하는 과정:

  1. 추가하려는 원소에 대해 k개의 해시 값을 계산
  2. 각 해시 값에 대응하는 비트를 1로 설정
예시: 원소 'apple' 추가 (m=18, k=3)

1. 해시 계산:
   h₁('apple') = 2
   h₂('apple') = 7
   h₃('apple') = 13

2. 비트 설정:
   이전: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
              ↓           ↓                       ↓
   이후: [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
이미 1인 비트는?

해시 값에 해당하는 비트가 이미 1이면 그대로 1로 유지됩니다. 이것이 긍정 오류가 발생하는 원인입니다.

3.2 원소 검사 (Query)​

원소가 집합에 속하는지 검사하는 과정:

  1. 검사하려는 원소에 대해 k개의 해시 값을 계산
  2. 각 해시 값에 대응하는 비트 값을 읽음
  3. 모든 비트가 1이면 "속한다" 판단
  4. 하나라도 0이면 "속하지 않는다" 판단
예시 1: 원소 'apple' 검사 (추가했던 원소)

1. 해시 계산:
   h₁('apple') = 2 → 비트[2] = 1 ✓
   h₂('apple') = 7 → 비트[7] = 1 ✓
   h₃('apple') = 13 → 비트[13] = 1 ✓

2. 결과: 모든 비트가 1 → "속한다" (정확!)
예시 2: 원소 'banana' 검사 (추가하지 않은 원소)

1. 해시 계산:
   h₁('banana') = 5 → 비트[5] = 0 ✗
   h₂('banana') = 8 → 비트[8] = 0 ✗
   h₃('banana') = 15 → 비트[15] = 0 ✗

2. 결과: 0이 존재 → "속하지 않는다" (정확!)
예시 3: 원소 'cherry' 검사 (긍정 오류 발생)

1. 해시 계산:
   h₁('cherry') = 2 → 비트[2] = 1 ✓ (다른 원소 때문에 1)
   h₂('cherry') = 7 → 비트[7] = 1 ✓ (다른 원소 때문에 1)
   h₃('cherry') = 13 → 비트[13] = 1 ✓ (다른 원소 때문에 1)

2. 결과: 모든 비트가 1 → "속한다" (오류! False Positive)

3.3 삭제 불가능한 이유​

블룸 필터에서 원소를 삭제할 수 없는 이유:

상황: 'apple'과 'apricot'이 추가되어 있고, 둘 다 비트[7]을 1로 설정함

비트 배열: [..., 0, 1, 0, ...]
                  ↑
               비트[7]

'apple'을 삭제하려고 비트[7]을 0으로 변경하면?
→ 'apricot' 검사 시 잘못된 결과 발생!
삭제가 필요한 경우

삭제 기능이 필요하면 Counting Bloom Filter 변형을 사용해야 합니다. 각 비트 대신 카운터를 사용하여 얼마나 많은 원소가 해당 위치를 사용하는지 추적합니다. 카운팅 필터(Counting filter)는 블룸 필터에서 필터를 재생성하지 않고도 원소의 삭제가 가능하도록 변형된 블룸 필터입니다.

4. 성능 특성​

4.1 시간 복잡도​

블룸 필터의 연산 시간은 집합에 포함된 원소 수와 무관합니다:

연산시간 복잡도설명
추가O(k)k개 해시 함수 계산 + k개 비트 설정
검사O(k)k개 해시 함수 계산 + k개 비트 읽기
원소가 10개든 10억 개든:
- 시간 복잡도는 동일하게 O(k)
- 집합 크기에 영향받지 않음
일반 해시 테이블과 비교

일반 해시 테이블:

  • 시간: O(1) 평균, O(n) 최악
  • 공간: O(n) - 모든 원소 저장

블룸 필터:

  • 시간: O(k) - 항상 일정
  • 공간: O(m) - 비트 배열만 저장 (원소 저장 안 함)
  • 트레이드오프: 공간 효율 vs 긍정 오류

4.2 공간 효율성​

블룸 필터는 실제 원소를 저장하지 않고 비트 배열만 사용합니다:

예시: 100만 개의 URL을 저장

일반 해시 테이블:
- 평균 URL 길이 100바이트
- 총 공간: 100MB

블룸 필터 (1% 오류율):
- 비트 배열 크기: ~1.2MB
- 약 80배 이상 공간 절약!

5. 오류 확률​

5.1 긍정 오류 확률 공식​

블룸 필터에서 긍정 오류(False Positive)가 발생할 확률:

n개 원소를 추가한 후, 긍정 오류 확률 p:

p ≈ (1 - e^(-kn/m))^k

변수:
- m: 비트 배열 크기
- k: 해시 함수 개수
- n: 추가된 원소 개수
- e: 자연상수 (약 2.71828)

5.2 확률 유도 과정​

1단계: 특정 비트가 0일 확률

원소 1개 추가 시 특정 비트가 0으로 남을 확률:
(1 - 1/m)

원소 n개 추가 후 특정 비트가 여전히 0일 확률:
(1 - 1/m)^(kn)

2단계: 특정 비트가 1일 확률

1 - (1 - 1/m)^(kn)

큰 m에 대해 근사:
≈ 1 - e^(-kn/m)

3단계: 모든 k개 비트가 1일 확률 (긍정 오류)

(1 - e^(-kn/m))^k

5.3 실전 예시​

설정: m = 10,000비트, k = 3개 해시, n = 1,000개 원소

p = (1 - e^(-3×1000/10000))^3
  = (1 - e^(-0.3))^3
  = (1 - 0.741)^3
  = (0.259)^3
  ≈ 0.017 = 1.7%

→ 약 1.7% 확률로 긍정 오류 발생
최적 해시 함수 개수

긍정 오류 확률을 최소화하는 최적 k 값:

k = (m/n) × ln(2) ≈ 0.693 × (m/n)

예: m=10,000, n=1,000 → k ≈ 7개

6. 장단점​

6.1 장점​

  • 공간 효율: 원소를 직접 저장하지 않아 메모리 사용 최소화
  • 빠른 속도: O(k) 시간에 추가/검사, 원소 개수와 무관
  • 부정 오류 없음: "없다"는 판단은 100% 정확
  • 집합 연산 간단: OR/AND 연산으로 합집합/교집합 구현

6.2 단점​

  • 긍정 오류: False Positive 발생 가능
  • 삭제 불가: 기본 블룸 필터는 원소 삭제 불가능
  • 크기 고정: 미리 비트 배열 크기를 결정해야 함
  • 원소 확인 불가: 어떤 원소가 들어있는지 확인 불가능

7. 요약​

핵심 개념
  1. 확률적 자료구조: 긍정 오류 가능, 부정 오류 불가능
  2. 구조: m비트 배열 + k개 해시 함수
  3. 연산: 추가 O(k), 검사 O(k)
  4. 오류율: (1 - e^(-kn/m))^k
  5. 삭제 불가: 기본 버전에서는 삭제 불가능
언제 사용할까?

블룸 필터는 다음 조건을 만족할 때 적합합니다:

  • 공간 절약이 중요함
  • 약간의 긍정 오류는 허용 가능
  • "없음"에 대한 확실한 보장이 필요
  • 원소 삭제가 필요 없음

참고​