Basic Concept
Counting Bloom Filter = Generalized Data Structure ของ Bloom Filter
ใช้ Test ว่า Count ของ Element ใดๆ < Threshold θ หรือไม่ (Given Sequence of Elements)
Generalized Form → False Positives Possible, No False Negatives
Query Returns: "Possibly ≥ θ" หรือ "Definitely < θ"
Algorithm Description
- Parameters: n, k เหมือน Bloom Filter, m = จำนวน Counters (ขยายจาก m Bits)
- Empty Filter: m Counters ทั้งหมด = 0
- k Hash Functions: Map Element → m Counter Positions (Uniform Random)
- k = Constant ≪ m, Proportional to Elements to Add
Insert Element
Hash Element ด้วย k Functions → k Array Positions → Increment Counters by 1 ทุก Position
Query Element with Threshold θ
- Hash Element → k Counter Positions
- ถ้า Counter ใด < θ → Count Definitely < θ (เพราะถ้า ≥ θ ทุก Counter จะ ≥ θ)
- ถ้า All Counters ≥ θ → Either Count ≥ θ จริง, หรือ False Positive (Counters ≥ θ โดยโชค)
- False Positive = All ≥ θ แต่ Count จริง < θ → Minimize เหมือน Bloom Filter
สรุป
Counting Bloom Filter = Bloom Filter + Counters แทน Bits
รองรับ: Insert, Delete (Decrement), Count Threshold Queries
No False Negatives, False Positives Possible
Space: m Counters (Typically 4-bit) แทน m Bits
