절충할 수 있는 블룸 필터에 대한 세 가지 성능 메트릭이 있습니다. 계산 또는 실행 시간(해시 함수 수 k에 해당), 필터 크기(비트 수 m에 해당), 오류 확률(해시 함수 수에 해당) 위양성 비율
f =(1 − p)k )
블룸 필터(BF)는 조회 성능과 공간 효율성을 향상시키기 위해 오류 허용치를 도입합니다. Bloom 필터는 true 또는 false를 반환합니다. 따라서 Bloom 필터의 결과는 참양성, 거짓양성, 참음성, 거짓음성 중 하나에 속합니다. 블룸 필터에 거짓 긍정이 포함된 최대 수입니다. 거짓 긍정과 거짓 부정은 시스템에 오버헤드를 일으킵니다. Bloom 필터는 요소의 정보를 저장하기 위해 배열을 구현합니다. 거짓 긍정은 다음과 같이 정의됩니다. 요소가 있을 때 Bloom 필터가 true를 반환하는 경우. 마찬가지로 거짓 부정은 다음과 같이 정의됩니다. 블룸 필터는 요소를 보유할 때 거짓을 반환합니다. 따라서 Bloom 필터는 확률적 데이터 구조에 속합니다.
블룸 필터 크기 및 해시 함수 수
블룸 필터의 크기가 너무 작으면 곧 모든 비트 필드가 '1'로 바뀌고 블룸 필터가 모든 입력 값에 대해 '거짓 긍정'을 반환한다는 것을 이해합니다. 따라서 블룸 필터의 크기는 매우 중요하거나 중요한 결정입니다. 필터가 클수록 오탐지가 적고 필터가 작습니다.
따라서 블룸 필터의 크기는 전적으로 '가양성 오류율'을 기반으로 한다는 결론을 내릴 수 있습니다.
또 다른 중요한 매개변수는 우리가 사용할 해시 함수의 양을 결정하는 것입니다. 우리가 구현하는 해시 함수가 많을수록 블룸 필터는 느려지고 더 빨리 채워집니다. 그러나 너무 적으면 많은 오탐으로 인해 어려움을 겪을 수 있습니다.
필터 크기 m, 해시 함수 수 k, 삽입된 요소 수 n을 기반으로 다음 공식을 사용하여 가양성 오류율 p를 계산할 수 있습니다.
p≈(1-e (-kn/m) ) k
우리는 실제로 m과 k가 무엇인지 결정해야 합니다. 따라서 오류 허용 오차 값 p와 요소 수 n을 직접 설정하거나 수정하면 다음 공식을 구현하여 이러한 매개변수를 계산할 수 있습니다.
m=(-n ln p)/(ln 2) 2
k=(m/n)*(ln 2)