Blocked Bloom Filter Overview
- เลือก Memory Block ก่อน
- ในแต่ละ Block ใช้ Local Bloom Filter
- อาจทำให้ Memory Blocks Imbalance
- Efficient แต่ False Positive Rate (FPR) แย่กว่า Standard
- ทฤษฎี: Blocked Bloom Filters ควรมี FPR เท่า Standard Bloom Filters ขนาดเดียวกัน
- ประกอบด้วย Sequence ของ Blocks (b) ขนาดเล็กกว่า Standard (แต่ละ Block Fit 1 Cache Line)
- ต่างจาก Partition Schemes ที่กระจาย Bits ไป Block ต่างกัน
Implementation Techniques
1. Bit Patterns (pat)
แทน Set k Bits ด้วย k Hash Functions → ใช้ 1 Hash Function เลือก Precomputed Pattern จาก Table ของ Random k-bit Patterns (Width = B)
Table มัก Fit ใน Cache → 1 Small Hash Value + Few SIMD Instructions
Transfer Bloom Filter: Table ไม่ต้อง Include Explicitly → Reconstruct จาก Seed Value
ข้อเสีย: Table Collision (2 Elements Hash ไป Pattern เดียวกัน) → FPR เพิ่มขึ้น
2. Multiplexing Patterns
ปรับปรุง: Bitwise-OR x Patterns ที่มี Average k/x Set Bits → Pattern Variety มากขึ้นจาก Table เดียว
3. Multi-Blocking
Query Access X Bloom Filter Blocks, Set/Test k/X Bits ต่อ Block
(k ไม่หาร X ลงตัว → Set Extra Bit ใน First k mod X Blocks)
ดีกว่าเพียงเพิ่ม Block Size เป็น X×B: Introduce Variety มากขึ้น
Expected 1-bits/Block เหมือนเดิม แต่ Consider แค่ k/X Bits/Block → FPR ดีขึ้น
สรุป
Blocked Bloom Filters = Cache-Friendly Bloom Filters
Techniques: Bit Patterns, Multiplexing, Multi-Blocking
Trade-off: Implementation Simplicity/Cache Efficiency ↔ FPR
