Performance Metrics (เมตริกประสิทธิภาพ) ของ Bloom Filters

3 Performance Metrics (Trade-off สามทาง)

1. Computation/Execution Time ↔ จำนวน k Hash Functions
2. Filter Size ↔ จำนวน m Bits
3. Error Probability ↔ False Positive Rate f = (1 - p)^k

Bloom Filter = Probabilistic Data Structure
Result: True Positive, False Positive, True Negative, False Negative
False Positive = Overhead หลัก (False Negative = 0 ใน Standard Bloom Filter)

Bloom Filter Size และ Number of Hash Functions

Size เล็กเกินไป → Bits กลายเป็น 1 ทั้งหมด → False Positive ทุก Input
→ Size = Critical Decision

Larger Filter → Less False Positives
Smaller Filter → More False Positives
→ Size Based on Target False Positive Error Rate

Hash Functions (k): มาก → Slow + Fill Up Fast, น้อย → Many False Positives

Formulas

False Positive Rate p ≈ (1 - e^-kn/m)^k

Given Target p และ n (Elements):

m = (-n ln p) / (ln 2)²
k = (m/n) * ln 2

Optimal k (สำหรับ m, n ที่กำหนด)

k_opt = (m/n) ln 2 → Minimizes False Positive Rate
ที่ k_opt: p_min ≈ (0.6185)^m/n

Rule of Thumb

• m/n ≈ 10 bits/element → p ≈ 1%
• m/n ≈ 14 bits/element → p ≈ 0.1%
• k ≈ 7 (เมื่อ m/n=10), k ≈ 10 (เมื่อ m/n=14)