Counter Size (ขนาดเคาน์เตอร์)
- ต้องเลือก Counters ใหญ่พอป้องกัน Overflow
- Poisson Approximation แนะนำ: 4 bits/counter
- Average Load (k = (ln 2)m/n Counters) = ln 2 ≈ 0.693
- P(Counter Load ≥ 16) ≈ e-ln2 (ln 2)16 / 16! ≈ 6.78×10-17 (Extremely Low)
- 4 bits/counter = Standard สำหรับ Comparisons
Counter Overflow (ล้นของเคาน์เตอร์)
- Counter Overflow → ถึง Max Value
- False Negative เกิดได้ก็ต่อเมื่อ Counter ลดลงมาที่ 0 แทนที่จะคง Nonzero
- Expected Time to False Negative = Very Large แต่ต้องคำนึงถึงสำหรับ Applications ที่ห้าม False Negatives
- ป้องกัน Overflow: Counter Size ใหญ่พอ → 4 bits/counter พอแล้ว
สรุป
Counting Bloom Filters ใช้ 4-bit Counters เป็นมาตรฐาน
Overflow Probability ต่ำมาก (≈10-17)
False Negative จาก Overflow = Rare Event แต่ Critical สำหรับบาง Applications
