- 먼저 메모리 블록을 선택합니다.
- 그런 다음 각 블록 내에서 로컬 블룸 필터를 선택합니다.
- 메모리 블록 간의 불균형을 일으킬 수 있음
- 이 필터는 효율적이지만 FPR(오탐지율)이 낮습니다.
- 처음에 차단된 블룸 필터는 동일한 크기의 표준 블룸 필터와 동일한 FPR(False Positive Rate)을 가져야 합니다.
- 차단된 블룸 필터는 각각 하나의 캐시 라인에 맞는 표준 블룸 필터(블룸 필터 블록)보다 비교적 적은 블록 b의 시퀀스로 구성됩니다.
- Blocked Bloom 필터 체계는 각 비트가 다른 블록에 삽입되는 파티션 체계와 구별됩니다.
차단된 블룸 필터는 다음과 같은 방식으로 구현됩니다 -
비트 패턴(pat)
이 주제에서는 미리 계산된 비트 패턴을 구현하는 차단된 블룸 필터를 구현하는 방법에 대해 설명합니다. k 개의 해시 함수 평가를 통해 k 비트를 설정하는 대신 단일 해시 함수는 너비 B의 임의 k비트 패턴 테이블에서 미리 계산된 패턴을 선택합니다. 대부분의 경우 이 테이블은 캐시에 맞습니다. 이 솔루션을 사용하면 하나의 작은(비트 측면에서) 해시 값만 필요하고 몇 가지 SIMD(Single Instruction Multiple Data) 명령어를 사용하여 작업을 구현할 수 있습니다. 블룸 필터를 전송할 때 테이블을 데이터에 명시적으로 포함할 필요는 없지만 시드 값을 구현하여 재구성할 수 있습니다.
비트 패턴 방법의 주요 단점은 두 요소가 동일한 패턴으로 해시될 때 테이블 충돌을 일으킬 수 있다는 것입니다. 이로 인해 FPR이 증가합니다.
다중화 패턴
이 아이디어를 다시 한 번 개선하기 위해 평균 k/x 세트 비트 수로 x 패턴을 비트 또는 처리하여 단일 테이블에서 더 다양한 패턴을 얻을 수 있습니다.
다중 차단
FPR을 개선하는 데 도움이 되는 또 하나의 변형을 다중 차단이라고 합니다. 쿼리 작업이 X Bloom 필터 블록에 액세스하여 각 블록에서 각각 k/X 비트를 설정하거나 테스트하도록 허용합니다. (k를 X로 나눌 수 없는 경우 첫 번째 k mod X 블록에 추가 비트를 설정합니다.) 다중 차단은 블록 크기를 XB(B-각 블록 크기)로 늘리는 것보다 성능이 더 좋습니다. 방법. 설정된 비트를 여러 블록으로 나누면 블록당 예상되는 1비트 수가 동일하게 유지됩니다. 그러나 요소에 액세스할 때 각 참여 블록에서 k/X 비트만 고려됩니다.