Bloom 필터 요약

1 Overview
    Bloom filter 는 최초 로 Burton Howard Bloom 이 제기 한 것 으로 구성원 이 특정한 집합 에 존재 하 는 지 여 부 를 판단 하 는 데이터 구조 이다.Bloom filter 의 판단 은 확률 론 에 기초 합 니 다.

한 멤버 가 집합 에 존재 한다 면 Bloom filter 는 휴가 (즉 존재 하지 않 음) 로 돌아 가지 않 는 다. 즉, false negative 는 불가능 하 다 는 것 이다.

한 멤버 가 실제로 집합 에 존재 하지 않 는 다 면 Bloom filter 는 실제 (즉 존재) 로 돌아 갈 수 있 으 며, 이 는 false positive 라 고 불 린 다.

    Bloom filter 는 보통 m 비트 를 포함 하 는 비트 그룹 (bit array) 으로 구현 되 며, 모든 비트 의 초기 값 은 0 입 니 다.Bloom filter 는 다음 두 가지 유형의 작업 을 지원 합 니 다.

add。구성원 을 Bloom filter 에 추가 합 니 다.이 구성원 을 매개 변수 로 k 개의 색인 함수 (index functions) 를 호출 하여 k 개의 배열 의 색인 값 을 얻 고 수치 범 위 는 [0, m) 이 며, 그 다음 에 비트 배열 의 대응 위 치 를 1 로 설정 합 니 다.

query. 한 구성원 이 Bloom filter 에 추가 되 었 는 지 판단 합 니 다. 이 구성원 을 매개 변수 로 k 개의 색인 함 수 를 호출 하여 k 개의 배열 의 색인 값 을 얻 은 다음 이 색인 값 에 따라 자릿수 그룹 을 검사 합 니 다. 비트 배열 의 모든 대응 위치 가 1 일 때 이 구성원 이 이미 존재 한다 고 생각 합 니까?

    query 의 결과 가 진짜 (즉 positive) 라면 실제로 다음 과 같은 두 가지 가능성 이 존재 합 니 다.

이 멤버 는 이미 집합 에 추가 되 었 다. 즉, 이 멤버 가 확실히 존재 한 다 는 것 이다.

이 멤버 는 집합 에 추가 되 지 않 았 으 나 query 과정 에서 검사 한 모든 위 치 는 1 (추 가 된 다른 멤버 로 인해) 로 설정 되 었 습 니 다. 이 경우 false positive 라 고 합 니 다.

    전통 적 인 Bloom filter 는 집합 에서 멤버 를 삭제 하 는 것 을 지원 하지 않 습 니 다. Bloom filter 에 추 가 된 모든 멤버 에 게 는 실제 적 으로 비트 배열 의 k 비트 를 1 로 설정 합 니 다. 이 비트 를 0 으로 초기 화하 면 Bloom filter 에서 멤버 를 삭제 할 수 있 지만, 이러한 부작용 은 다른 멤버 들 에 게 도 영향 을 미 칠 수 있 습 니 다. 다른 멤버 들 도 이 를 반영 할 수 있 기 때 문 입 니 다.0 자리 중 한 자리 또는 여러 자리 로 설정 하여 false negatives 를 가 져 옵 니 다. Bloom filter 의 경우 false negatives 는 허용 되 지 않 습 니 다. Counting Bloom filter 는 계수 가 적용 되 어 reove 작업 을 지원 합 니 다.
    Bloom filter 에서 사용 하 는 k 개의 index functions 는 hash functions 라 고도 부 릅 니 다. 이들 은 보통 서로 독립 된 것 으로 가정 되 고 반환 값 은 가능 한 수치 범위 내 에서 균일 하 게 분포 되 어 있 습 니 다 (이것 은 다음 과 같은 일련의 수학 적 증명 의 기초 입 니 다).
 
2 The Math
    Bloom filter 의 기본 개념 은 복잡 하지 않 습 니 다. 다음은 query 작업 이 추가 되 지 않 은 구성원 에 게 positive (즉 false positive) 로 돌아 갈 확률 을 분석 하 겠 습 니 다.
    p 가 자릿수 그룹 중 한 명 이 1 일 확률 이 라 고 가정 하면 false positive 의 확률 은 pk 입 니 다. n 이 Bloom filter 에 추 가 된 멤버 개수 라면 p = 1 – (1 – 1 / m) nk 는 일련의 추 도 를 통 해 p 개 월 (1 – e - kn / m) k 를 얻 을 수 있 습 니 다. k = m / n * ln2 일 때 (ln 즉 loge), p 는 최소 값 입 니 다. 예 를 들 어 k = 8, m / n = 10 시 false positive 의 이론 값 은 0.00846 입 니 다. 다음은 false positive 를 계산 하 는 인 스 턴 스 코드 입 니 다.
 

public static double calculateFalsePositiveProbability(int k, int m, int n) {
	return Math.pow((1 - Math.exp(-k * (double) n  / (double) m)), k);
}

 
 
 
    일부 응용 에 있어 서 false positive 의 확률 은 Bloom filter 의 정확성 을 충분히 판단 하 는 지표 이다. Peter C. Dillinger 와 Panagiotis Manolios 는 Bloom Filters in Probablistic Verfification 논문 에서 query 과정 에서 의 불확실 성에 대해 state omission 은 더욱 적합 한 지표 라 고 지적 했다. 관심 있 는 독자 들 이 이 이론 을 읽 는 것 을 권장 한다.글, 수학 지식 도 복습 할 수 있 습 니 다.
 
3 Refinement
    So far, so good. 일반적인 HashMap 에 비해 Bloom filter 는 메모리 에 key 와 value 를 저장 하지 않 고 자릿수 그룹 에 있 는 몇 개의 비트 를 저장 하면 됩 니 다. 이것 은 메모리 사용 에 있어 서 큰 절약 입 니 다. 물론 전 제 는 일정한 확률 의 false positives 를 용인 하 는 것 입 니 다. 그러나 전 통 된 Bloom filter 는 다음 과 같은 두 가지 심각 한 결함 이 있 습 니 다.

충분 한 false positive 확률 을 확보 하기 위해 보통 색인 함수 의 개수 k 가 비교적 크다 (예 를 들 어 10 대, 심지어 몇 십 이지 만 보통 32 를 초과 하지 않 는 다). 이렇게 많은 random, uniform and independent 의 색인 함 수 를 찾 을 수 있 는 것 은 쉬 운 일이 아니다.

수량 이 많은 색인 함수 로 인해 add 와 query 의 성능 이 높 지 않 습 니 다.

    Peter C. Dillinger 와 Panagiotis Manolios 는 논문 에서 fingerprinting Bloom filter 는 색인 함수 의 개 수 를 효과적으로 줄 이 고 정확성 에 미 치 는 영향 을 무시 할 수 있다 고 지적 했다. 이것 은 전통 적 인 Bloom filter 에 있어 서 중대 한 개선 이 라 고 주장 했다. 필 자 는 그 중에서 소개 한 triple hashing 을 사용 하여 효과 가 비교적 뚜렷 하 다 고 주장 했다.
 
4 Implementation
    Google 이 자바 로 구현 하 는 Bloom filter 라면 자바 - bloomfilter 는 가장 쉽게 찾 을 수 있 는 구현 중 하나 일 수 있 습 니 다. 기 존의 Bloom filter 알고리즘 을 사용 합 니 다. k 개의 색인 함수 (기본 값 은 MD5) 를 사용 합 니 다. 색인 함수 가 계산 할 때 인자 의 소금 (salting) 을 다 를 뿐 입 니 다. 필 자 는 자바 - bloomfilter 의 성능 이 향상 되 어야 한다 고 생각 합 니 다.
    Hadoop common 의 util 패키지 에 도 Bloom Filter 의 실현 을 제공 합 니 다. 또한 hash 패 키 지 는 Jenkins Hash 와 MurmurHash 두 개의 Hash 알고리즘 을 제공 합 니 다. 필 자 는 Hadoop 의 Bloom filter 의 실현 방식 이 fingerprinting Bloom filter 와 유사 하 다 고 생각 하지만 double hashing 이나 triple hashing 을 사용 하지 않 았 습 니 다.
    또한, 자릿수 그룹의 실현 방식 에 대해 서 는 자바 util. bitset 를 사용 하 는 것 이 가장 직접적인 생각 일 수 있 습 니 다. 그러나 필 자 는 처리 한 데이터 의 양 이 많 거나 성능 에 대한 요구 가 높 으 면 자바 util. bitset 를 사용 하 는 것 을 권장 하지 않 습 니 다. 자바 util. bitset 의 메모리 사용 방식, 전체 성능 이 이상 적 이지 않 기 때 문 이 라 고 생각 합 니 다.
 
 
5 Reference

Bloom Filters in Probablistic Verfification. Peter C.Dillinger and Panagiotis Manolios

Hadoop 의 Bloom filter 구현.http://hadoop.apache.org/common/

java-bloomfilter.  http://code.google.com/p/java-bloomfilter/