แนวคิดพื้นฐาน
ตัวกรอง Counting Bloom ถูกกำหนดให้เป็นโครงสร้างข้อมูลทั่วไปของตัวกรอง Bloom ที่นำมาใช้เพื่อทดสอบว่าจำนวนการนับขององค์ประกอบที่กำหนดนั้นน้อยกว่าเกณฑ์ที่กำหนดเมื่อกำหนดลำดับขององค์ประกอบหรือไม่ ตามรูปแบบทั่วไปของตัวกรอง Bloom มีความเป็นไปได้ที่จะจับคู่ผลบวกที่ผิดพลาด แต่ไม่มีโอกาสเกิดผลลบลวง กล่าวคือ แบบสอบถามจะส่งกลับ "อาจสูงกว่าหรือเท่ากับเกณฑ์" หรือ "น้อยกว่าเกณฑ์" อย่างแน่นอน
คำอธิบายอัลกอริทึม
- พารามิเตอร์ส่วนใหญ่ที่ใช้ภายใต้ตัวกรองการนับจำนวนบาน ถูกกำหนดแบบเดียวกันกับตัวกรอง Bloom เช่น n, k m แสดงเป็นจำนวนตัวนับในตัวกรอง Counting Bloom ซึ่งเป็นการขยาย m บิตในตัวกรอง Bloom
- ตัวกรอง Counting Bloom ที่ว่างเปล่าถูกตั้งค่าเป็นตัวนับ m ทั้งหมดเริ่มต้นเป็น 0
- คล้ายกับตัวกรอง Bloom จะต้องมีการกำหนดฟังก์ชันแฮชต่างๆ k ฟังก์ชัน ซึ่งแต่ละฟังก์ชันมีหน้าที่ในการแมปหรือแฮชองค์ประกอบชุดหนึ่งไปยังตำแหน่งอาร์เรย์ตัวนับ m ตำแหน่งใดตำแหน่งหนึ่ง ทำให้เกิดการกระจายแบบสุ่มที่สม่ำเสมอ มันก็เหมือนกันที่ k เป็นค่าคงที่ ซึ่งน้อยกว่า m มาก ซึ่งเป็นสัดส่วนกับจำนวนขององค์ประกอบที่จะผนวก
- ลักษณะทั่วไปหลักของตัวกรอง Bloom คือการเพิ่มองค์ประกอบ ในการผนวกองค์ประกอบ แทรกลงในฟังก์ชันแฮช k แต่ละฟังก์ชันเพื่อรับตำแหน่งอาร์เรย์ k และเพิ่มตัวนับ 1 ที่ตำแหน่งเหล่านี้ทั้งหมด
- หากต้องการค้นหาองค์ประกอบที่มีขีดจำกัด θ (ตรวจสอบว่าจำนวนนับขององค์ประกอบน้อยกว่า θ หรือไม่) ให้แทรกลงในฟังก์ชัน k hash แต่ละฟังก์ชันเพื่อให้ได้ตำแหน่งตัวนับ k
- หากตัวนับใดๆ ที่ตำแหน่งเหล่านี้น้อยกว่า θ จำนวนองค์ประกอบที่นับจะน้อยกว่า θ อย่างแน่นอน หากสูงกว่าและเท่ากัน ตัวนับที่เกี่ยวข้องทั้งหมดจะสูงกว่าหรือเท่ากับ θ หลี่>
- หากทั้งหมดสูงกว่าหรือเท่ากับ θ การนับจะสูงกว่าหรือเท่ากับ θ จริงๆ หรือตัวนับมีโอกาสสูงกว่าหรือเท่ากับ θ โดยบังเอิญ
- หากทั้งหมดสูงกว่าหรือเท่ากับ θ แม้ว่าจำนวนจะน้อยกว่า θ สถานการณ์นี้จะถูกกำหนดให้เป็นผลบวกลวง เช่นเดียวกับตัวกรอง Bloom ก็ควรย่อให้เล็กสุดด้วย
