ตัวกรองบลูมที่ถูกบล็อก

• เราเลือกบล็อกหน่วยความจำก่อน
• จากนั้นเราเลือก Bloom Filter ภายในแต่ละบล็อก
• อาจทำให้เกิดความไม่สมดุลระหว่างบล็อกหน่วยความจำ
• ตัวกรองนี้มีประสิทธิภาพ แต่มีอัตราการบวกลวง (FPR) ต่ำ
• ในตัวอย่างแรก ตัวกรอง Bloom ที่ถูกบล็อกควรมี FPR (False Positive Rate) เดียวกันกับตัวกรอง Bloom มาตรฐานที่มีขนาดเท่ากัน
• Blocked Bloom Filter ประกอบด้วยลำดับของบล็อก b ซึ่งค่อนข้างน้อยกว่าตัวกรอง Bloom มาตรฐาน (บล็อกตัวกรอง Bloom) ซึ่งแต่ละอันจะพอดีกับแคชบรรทัดเดียว
• รูปแบบตัวกรอง Bloom ที่ถูกบล็อกจะแตกต่างจากรูปแบบพาร์ติชั่น โดยที่แต่ละบิตจะถูกแทรกลงในบล็อกที่ต่างกัน

ตัวกรอง Bloom ที่ถูกบล็อกมีการใช้งานในลักษณะดังต่อไปนี้ -

รูปแบบบิต (แพท)

ในหัวข้อนี้ เราจะหารือเกี่ยวกับการใช้ตัวกรอง Bloom ที่ถูกบล็อกซึ่งนำรูปแบบบิตที่คำนวณไว้ล่วงหน้ามาใช้ แทนที่จะตั้งค่า k บิตผ่านการประเมินฟังก์ชัน k แฮช ฟังก์ชันแฮชเดี่ยวจะเลือกรูปแบบที่คำนวณล่วงหน้าจากตารางรูปแบบ k-bit แบบสุ่มที่มีความกว้าง B ในหลายกรณี ตารางนี้จะพอดีกับแคช ด้วยโซลูชันนี้ จำเป็นต้องมีค่าแฮชขนาดเล็กเพียงค่าเดียว (ในรูปของบิต) และการดำเนินการสามารถใช้งานได้โดยใช้คำสั่ง SIMD (คำสั่งเดียวหลายข้อมูล) เพียงเล็กน้อย ในขณะที่ถ่ายโอนตัวกรอง Bloom ไม่จำเป็นต้องรวมตารางในข้อมูลอย่างชัดเจน แต่สามารถสร้างใหม่ได้โดยใช้ค่าเมล็ดพันธุ์

ข้อเสียเปรียบหลักของวิธีการรูปแบบบิตคือสององค์ประกอบอาจทำให้เกิดการชนกันของตารางเมื่อถูกแฮชไปยังรูปแบบเดียวกัน ทำให้ FPR เพิ่มขึ้น

รูปแบบมัลติเพล็กซ์

ในการปรับแต่งแนวคิดนี้อีกครั้ง เราสามารถบรรลุรูปแบบที่หลากหลายมากขึ้นจากตารางเดียวโดยใช้รูปแบบ x ระดับบิตหรืออิงตามจำนวนชุดบิตเฉลี่ย k/x

การบล็อกหลายจุด

อีกตัวแปรหนึ่งที่ช่วยปรับปรุง FPR จะแสดงเป็นที่เรียกว่า multi-blocking เราอนุญาตให้การดำเนินการค้นหาเข้าถึงบล็อกตัวกรอง X Bloom การตั้งค่าหรือทดสอบบิต k/X ตามลำดับในแต่ละบล็อก (เมื่อ k ไม่หารด้วย X เราจะตั้งค่าบิตพิเศษในบล็อก k mod X แรก) การบล็อกหลายรายการทำได้ดีกว่าการเพิ่มขนาดบล็อกเป็น XB (ขนาดบล็อกแต่ละบล็อก B) เนื่องจากมีการแนะนำสิ่งนี้ให้หลากหลายมากขึ้น ทาง. หากเราแบ่ง set bits ออกเป็นหลายๆ block จำนวนที่คาดไว้คือ 1 bit ต่อ block เหมือนเดิม อย่างไรก็ตาม จะพิจารณาเฉพาะบิต k/X ในแต่ละบล็อกที่เข้าร่วม เมื่อเข้าถึงองค์ประกอบ