블룸 필터 예제로 이해하기

• 블룸 필터는 메모리 효율적으로 집합 내에 요소의 존재 여부를 빠르게 확인하는 확률적 자료구조임
• 요소가 집합에 확실히 없는지, 또는 있을지도 모른다고만 알려주며, 가짜 양성의 확률이 존재함
• 기본 구조는 비트 벡터와 여러 해시 함수를 사용하여 각 요소에 해당하는 비트를 1로 설정함
• 필터 크기와 해시 함수 개수에 따라 오차율과 성능이 결정되며, 활용 용도에 맞게 조정 가능함
• 추천 해시 함수 및 최적 설정 방법, 공간 효율성, 실제 적용사례 등도 소개됨

블룸 필터란 무엇인가

• 블룸 필터는 특정 요소가 집합에 존재하는지 빠르고 메모리 효율적으로 판별하는 자료구조임
• 이 효율성을 위하여 블룸 필터는 확률적 자료구조로, 검사 결과가 "집합에 확실히 없음" 또는 "집합에 있을 수도 있음"으로 나뉨
• 블룸 필터의 핵심 구조는 비트 벡터임
• 원소를 추가할 때 각 원소를 여러 번 해시해서 그 인덱스의 비트를 1로 설정함
• 각 해시 함수별로 나온 인덱스에 해당하는 비트가 모두 1일 경우 "존재할 수도 있음"이라고 판별하고, 그렇지 않으면 "확실히 없음"으로 처리함

동작 원리 예시

• 여러 개의 해시 함수(ex: Fnv, Murmur)를 통해 원소를 여러 개 비트 인덱스로 매핑함
• 원소 추가 시 계산된 인덱스의 비트를 1로 변경함
• 특정 원소의 존재 여부를 검사할 때, 같은 해시 함수와 동일한 방식의 인덱스가 모두 1이면 "존재할 수도 있음"으로 간주함
• 만약 하나라도 해당 비트가 0이면 "집합에 없음"으로 확실히 판단 가능함
• 이로 인해, 거짓 긍정(가짜 양성) 의 가능성이 생김

고급 주제

주의: 작성자는 실제로 대규모 서비스에 블룸 필터를 적용해 본 경험이 없음

해시 함수 선택

• 독립적이고 균등 분포를 가지는 해시 함수가 권장됨
• 암호학적 해시 함수(sha1 등)는 느리기 때문에 적합하지 않음
• 빠르고 단순한 해시 함수 예시는: Murmur, xxHash, Fnv, HashMix 등임
• 실제 사례에서는 md5에서 murmur로 변경 시 800% 이상 속도 향상을 경험함

블룸 필터의 크기 결정

• 필터 크기(m) 가 클수록 거짓 긍정률이 줄어듦
• 거짓 긍정률은 보통 (1-e^(-kn/m))^k으로 근사 가능함
• 기대 원소 수(n), 필터 크기(m), 해시 함수 개수(k)를 적절히 정해야 함

해시 함수 개수는?

• 해시 함수 수가 많을수록 속도가 느려지고 필터가 더 빨리 채워짐
• 너무 적으면 거짓 긍정률이 높아짐
• 이상적인 k는 *(m/n)ln(2)*로 계산됨
• 설계시 다음 절차로 진행:
  • 기대 원소 수 n을 추정
  • 비트수 m을 정하고
  • 최적 k를 산출
  • 원하는 오차율이 나오는지 확인, 안 되면 m을 조절

성능 및 공간 효율

• 블룸 필터에서 원소 추가/존재 검사는 O(k)의 시간 복잡도 가짐
• 공간 효율성은 오차율 허용 범위와 원소 범위에 따라 결정됨
• 원소 범위를 대략적으로나마 예측하지 못하면 해시 테이블이나 확장형 블룸 필터가 나을 수 있음

활용 사례

• 자세한 활용예는 Wikipedia 참고
• C. Titus Brown는 블룸 필터의 바이오인포매틱스 적용사례를 제시함

참고 자료

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — 블룸 필터 개요 논문임
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida 등: Scalable Bloom Filters