ในทางคอมพิวเตอร์ตัวกรองบลูม (Bloom filter) คือ โครงสร้างข้อมูลเชิงความน่าจะ เป็นที่มีประสิทธิภาพด้านพื้นที่ จัดเก็บข้อมูล ซึ่งคิดค้นโดยเบอร์ตัน ฮาวาร์ด บลูมในปี 1970 โดยใช้เพื่อทดสอบว่าองค์ประกอบ ใด เป็นสมาชิกของเซต หรือไม่ การจับคู่ ที่ผิดพลาดแบบบวก (false positive)เป็นไปได้ แต่ การจับคู่ที่ผิดพลาดแบบลบ (false negative ) นั้นเป็นไปไม่ได้ กล่าวคือ การค้นหาจะส่งคืนค่า "อาจอยู่ในเซต" หรือ "ไม่อยู่ในเซตอย่างแน่นอน" สามารถเพิ่มองค์ประกอบลงในเซตได้ แต่ไม่สามารถลบออกได้ (แม้ว่าปัญหานี้จะสามารถแก้ไขได้ด้วยตัวกรองบลูมแบบนับจำนวน ) ยิ่งเพิ่มรายการมากเท่าใด โอกาสที่จะเกิดการจับคู่ที่ผิดพลาดแบบบวกก็จะยิ่งมากขึ้นเท่านั้น

Bloom เสนอเทคนิคนี้สำหรับแอปพลิเคชันที่ปริมาณข้อมูลต้นทางจะต้องการหน่วยความจำจำนวนมากจนไม่สามารถใช้งานได้จริงหาก ใช้เทคนิค การแฮชแบบ ปราศจากข้อผิดพลาดแบบ "ดั้งเดิม" เขาให้ตัวอย่างอัลกอริทึมการแบ่งคำสำหรับพจนานุกรม 500,000 คำ ซึ่ง 90% เป็นไปตามกฎการแบ่งคำแบบง่าย แต่ 10% ที่เหลือต้องใช้การเข้าถึงดิสก์ที่มีราคาแพงเพื่อดึงรูปแบบการแบ่งคำเฉพาะ หากมีหน่วยความจำหลัก เพียงพอ สามารถใช้แฮชแบบปราศจากข้อผิดพลาดเพื่อกำจัดการเข้าถึงดิสก์ที่ไม่จำเป็นทั้งหมด ในทางกลับกัน หากมีหน่วยความจำหลักจำกัด เทคนิคของ Bloom จะใช้พื้นที่แฮชที่เล็กกว่า แต่ยังคงกำจัดการเข้าถึงที่ไม่จำเป็นส่วนใหญ่ได้ ตัวอย่างเช่น พื้นที่แฮชเพียง 18% ของขนาดที่จำเป็นสำหรับแฮชแบบปราศจากข้อผิดพลาดในอุดมคติยังคงกำจัดการเข้าถึงดิสก์ได้ 87% ^{[ 1 ]}

โดยทั่วไปแล้ว ต้องใช้บิตน้อยกว่า 10 บิตต่อองค์ประกอบเพื่อให้มีโอกาสเกิดผลบวกเท็จ 1% โดยไม่ขึ้นอยู่กับขนาดหรือจำนวนองค์ประกอบในชุด^{[ 2 ]}

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

ในการเพิ่มองค์ประกอบ ให้ป้อนองค์ประกอบนั้นลงใน ฟังก์ชันแฮช kฟังก์ชันเพื่อรับ ตำแหน่งในอาร์เรย์ kตำแหน่ง จากนั้นตั้งค่าบิตที่ตำแหน่งทั้งหมดเหล่านั้นให้เป็น 1

เพื่อทดสอบว่าองค์ประกอบอยู่ในชุดหรือไม่ ให้ป้อนองค์ประกอบนั้นไปยัง ฟังก์ชันแฮช kฟังก์ชันเพื่อรับตำแหน่งในอาร์เรย์k ตำแหน่ง หากบิต ใด ๆในตำแหน่งเหล่านั้นเป็น 0 แสดงว่าองค์ประกอบนั้นไม่อยู่ในชุดอย่างแน่นอน หากอยู่ในชุด บิตทั้งหมดจะต้องถูกตั้งค่าเป็น 1 เมื่อถูกแทรก หากบิตทั้งหมดเป็น 1 แสดงว่าองค์ประกอบนั้นอยู่ในชุดหรือบิตอาจถูกตั้งค่าเป็น 1 โดยบังเอิญระหว่างการแทรกองค์ประกอบอื่น ๆ ส่งผลให้เกิดผลลัพธ์ที่ผิดพลาดในตัวกรอง Bloom แบบง่าย ไม่มีวิธีใดที่จะแยกแยะระหว่างสองกรณีนี้ได้ แต่เทคนิคขั้นสูงกว่าสามารถแก้ไขปัญหานี้ได้

ข้อกำหนดในการออกแบบฟังก์ชันแฮชอิสระที่แตกต่างกันk ฟังก์ชันอาจเป็นอุปสรรคสำหรับ k ที่มีขนาดใหญ่ สำหรับฟังก์ชันแฮชที่ดีที่มีเอาต์พุตกว้าง ควรมีความสัมพันธ์น้อยมากหรือไม่มีเลยระหว่างบิตฟิลด์ที่แตกต่างกันของแฮชดังกล่าว ดังนั้นแฮชประเภทนี้จึงสามารถใช้เพื่อสร้างฟังก์ชันแฮช "ที่แตกต่างกัน" หลายฟังก์ชันได้โดยการแบ่งเอาต์พุตออกเป็นบิตฟิลด์หลายบิต หรืออีกทางหนึ่ง สามารถส่ง ค่าเริ่มต้นที่แตกต่างกัน kค่า (เช่น 0, 1, ..., k  − 1) ไปยังฟังก์ชันแฮชที่รับค่าเริ่มต้น หรือเพิ่ม (หรือต่อท้าย) ค่าเหล่านี้ลงในคีย์ สำหรับmและ/หรือk ที่มากขึ้น ความเป็นอิสระระหว่างฟังก์ชันแฮชสามารถผ่อนคลายได้โดยที่อัตราการเกิดผลบวกเท็จเพิ่มขึ้นเพียงเล็กน้อย^{[ 3 ]} (โดยเฉพาะอย่างยิ่งDillinger & Manolios (2004b)แสดงให้เห็นถึงประสิทธิภาพของการหา ค่าดัชนี kโดยใช้การแฮชแบบดับเบิลแฮ ช และ ทริปเปิลแฮชที่ได้รับการปรับปรุง ซึ่ง เป็นรูปแบบต่างๆ ของ การแฮชแบบดับเบิล แฮช ที่มีประสิทธิภาพคือตัวสร้าง ตัวเลขสุ่มแบบง่ายๆ ที่ใช้ค่าแฮชสองหรือสามค่าเป็นค่าเริ่มต้น)

การลบองค์ประกอบออกจาก Bloom filter แบบง่ายนี้เป็นไปไม่ได้ เพราะไม่มีวิธีใดที่จะบอกได้ว่าควรล้างบิต ใดใน k บิตที่องค์ประกอบนั้นแมปอยู่ แม้ว่าการตั้งค่าบิตใดบิตหนึ่งใน kบิตนั้นให้เป็นศูนย์จะเพียงพอที่จะลบองค์ประกอบนั้นได้ แต่ก็จะลบองค์ประกอบอื่นๆ ที่บังเอิญแมปกับบิตนั้นไปด้วย เนื่องจากอัลกอริทึมแบบง่ายนี้ไม่มีวิธีใดที่จะตรวจสอบได้ว่ามีการเพิ่มองค์ประกอบอื่นๆ ที่ส่งผลต่อบิตขององค์ประกอบที่จะถูกลบหรือไม่ การล้างบิตใดๆ จึงอาจทำให้เกิดผลลัพธ์ที่ผิดพลาดได้

การลบองค์ประกอบออกจาก Bloom filter เพียงครั้งเดียว สามารถจำลองได้โดยการใช้ Bloom filter ตัวที่สองซึ่งมีรายการที่ถูกลบออกไปแล้ว อย่างไรก็ตาม ผลลัพธ์ที่ผิดพลาดในฟิลเตอร์ตัวที่สองจะกลายเป็นผลลัพธ์ที่ผิดพลาดในฟิลเตอร์แบบผสม ซึ่งอาจไม่เป็นที่ต้องการ ในวิธีการนี้ การเพิ่มรายการที่ถูกลบออกไปก่อนหน้านี้กลับเข้าไปใหม่เป็นไปไม่ได้ เนื่องจากจะต้องลบออกจากฟิลเตอร์ "ที่ถูกลบออกไป" ก่อน

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

แม้ว่าจะมีความเสี่ยงต่อผลลัพธ์ที่ผิดพลาด (false positives) แต่ Bloom filter ก็มีข้อได้เปรียบด้านพื้นที่จัดเก็บข้อมูลมากกว่าโครงสร้างข้อมูลอื่นๆ สำหรับการแสดงชุดข้อมูล เช่นต้นไม้ค้นหาแบบไบนารีที่ปรับสมดุลตัวเอง (self-balancing binary search trees) , ไทร (tries) , ตารางแฮช (hash table ) หรืออาร์เรย์หรือรายการเชื่อมโยง แบบง่ายๆ ของรายการต่างๆ โครงสร้างข้อมูลส่วนใหญ่เหล่านี้จำเป็นต้องจัดเก็บอย่างน้อยรายการข้อมูลเอง ซึ่งอาจต้องการพื้นที่ตั้งแต่จำนวนบิตเล็กน้อยสำหรับจำนวนเต็มขนาดเล็ก ไปจนถึงจำนวนบิตที่ไม่จำกัด เช่น สำหรับสตริง ( ไทรเป็นข้อยกเว้น เนื่องจากสามารถใช้พื้นที่จัดเก็บร่วมกันระหว่างองค์ประกอบที่มีคำนำหน้าเท่ากันได้) อย่างไรก็ตาม Bloom filter ไม่ได้จัดเก็บรายการข้อมูลเลย และต้องมีวิธีการจัดเก็บแยกต่างหาก โครงสร้างแบบเชื่อมโยงจะทำให้เกิดค่าใช้จ่ายด้านพื้นที่เชิงเส้นเพิ่มเติมสำหรับตัวชี้ ในทางตรงกันข้าม Bloom filter ที่มีข้อผิดพลาด 1% และค่าk ที่เหมาะสมที่สุด ต้องการพื้นที่เพียงประมาณ 9.6 บิตต่อองค์ประกอบเท่านั้น โดยไม่คำนึงถึงขนาดขององค์ประกอบ ข้อได้เปรียบนี้มาจากการที่มันกะทัดรัด ซึ่งได้รับมาจากอาร์เรย์ และมาจากลักษณะเชิงความน่าจะเป็นของมัน อัตราผลลัพธ์ที่ผิดพลาด 1% สามารถลดลงได้ถึงสิบเท่าโดยการเพิ่มบิตเพียงประมาณ 4.8 บิตต่อองค์ประกอบ

อย่างไรก็ตาม หากจำนวนค่าที่เป็นไปได้มีน้อยและหลายค่าสามารถอยู่ในชุดได้ ตัวกรอง Bloom จะถูกแซงหน้าได้ง่ายโดยอาร์เรย์บิต แบบกำหนด ซึ่งต้องการเพียงบิตเดียวสำหรับแต่ละองค์ประกอบที่เป็นไปได้ ตารางแฮชจะได้รับข้อได้เปรียบด้านพื้นที่และเวลาหากเริ่มเพิกเฉยต่อการชนกันและจัดเก็บเฉพาะว่าแต่ละบัคเก็ตมีรายการหรือไม่ ในกรณีนี้ ตารางแฮชจะกลายเป็นตัวกรอง Bloom ที่มีk = 1 อย่างมีประสิทธิภาพ ^{[ 4 ]}

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

เพื่อให้เข้าใจถึงประสิทธิภาพการใช้พื้นที่ จึงควรเปรียบเทียบตัวกรอง Bloom ทั่วไปกับกรณีพิเศษเมื่อk = 1หากk = 1เพื่อรักษาอัตราการเกิดผลบวกเท็จให้ต่ำเพียงพอ ควรตั้งค่าบิตเพียงเศษส่วนเล็กน้อย ซึ่งหมายความว่าอาร์เรย์จะต้องมีขนาดใหญ่มากและมีศูนย์จำนวนมากปริมาณข้อมูลของอาร์เรย์เมื่อเทียบกับขนาดจึงต่ำ ตัวกรอง Bloom แบบทั่วไป ( k มากกว่า 1) อนุญาตให้ตั้งค่าบิตได้มากขึ้นในขณะที่ยังคงรักษาอัตราการเกิดผลบวกเท็จให้ต่ำ หาก เลือกพารามิเตอร์ ( kและm ) ได้ดี ประมาณครึ่งหนึ่งของบิตจะถูกตั้งค่า ^{[ 5 ]}และบิตเหล่านี้จะดูเหมือนสุ่ม ลดความซ้ำซ้อนและเพิ่มปริมาณข้อมูลให้สูงสุด

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

${\displaystyle 1-{\frac {1}{m}}.}$

ถ้าkคือจำนวนฟังก์ชันแฮช และแต่ละฟังก์ชันไม่มีความสัมพันธ์กันอย่างมีนัยสำคัญ แล้วความน่าจะเป็นที่บิตจะไม่ถูกตั้งค่าเป็น 1 โดยฟังก์ชันแฮชใดๆ ก็คือ

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}$

เราสามารถใช้เอกลักษณ์ที่รู้จักกันดีสำหรับe ^{−1 ได้}

${\displaystyle \lim _{m\to \infty }\left(1-{\frac {1}{m}}\right)^{m}={\frac {1}{e}}}$

สรุปได้ว่า สำหรับค่า mที่ มาก

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}=\left(\left(1-{\frac {1}{m}}\right)^{m}\right)^{k/m}\approx e^{-k/m}.}$

ถ้าเราใส่ค่าเข้าไปnค่า ความน่าจะเป็นที่บิตใดบิตหนึ่งยังคงเป็น 0 คือ

${\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}\approx e^{-kn/m};}$

ดังนั้น ความน่าจะเป็นที่ค่าจะเป็น 1 คือ

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}\approx 1-e^{-kn/m}.}$

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

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.}$

ถึงแม้จะไม่ถูกต้องอย่างเคร่งครัด เพราะมันสมมติว่าความน่าจะเป็นของการตั้งค่าแต่ละบิตเป็นอิสระต่อกัน อย่างไรก็ตาม หากสมมติว่าเป็นค่าประมาณที่ใกล้เคียง เราจะได้ว่าความน่าจะเป็นของผลบวกเท็จจะลดลงเมื่อm (จำนวนบิตในอาร์เรย์) เพิ่มขึ้น และจะเพิ่มขึ้นเมื่อn (จำนวนองค์ประกอบที่แทรกเข้าไป) เพิ่มขึ้น

ความน่าจะเป็นที่แท้จริงของผลบวกเท็จ โดยไม่ถือว่าเหตุการณ์เป็นอิสระต่อกัน คือ

${\displaystyle {\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{{kn \atop i}\right\}}$

โดยที่ {วงเล็บปีกกา} หมายถึง จำนวนส ^{เตอร์}ลิงประเภทที่สอง^{[ 6} ]

การวิเคราะห์ทางเลือกอื่นที่ได้มาซึ่งการประมาณค่าเดียวกันโดยไม่ต้องตั้งสมมติฐานเรื่องความเป็นอิสระนั้นได้มาจาก Mitzenmacher และ Upfal ^{[ 7 ]} หลังจากที่ เพิ่มรายการทั้งn รายการลงใน Bloom filter แล้ว ให้ qเป็นเศษส่วนของ บิต mบิตที่ตั้งค่าเป็น 0 (นั่นคือ จำนวนบิตที่ยังคงตั้งค่าเป็น 0 คือqm ) จากนั้น เมื่อทดสอบการเป็นสมาชิกขององค์ประกอบที่ไม่ได้อยู่ในเซต สำหรับตำแหน่งอาร์เรย์ที่กำหนดโดย ฟังก์ชันแฮช k ฟังก์ชันใดๆ ความน่าจะเป็นที่บิตนั้นถูกตั้งค่าเป็น 1 คือดังนั้น ความน่าจะเป็นที่ ฟังก์ชันแฮช k ฟังก์ชันทั้งหมด พบว่าบิตของฟังก์ชันนั้นตั้งค่าเป็น 1 คือยิ่ง ไปกว่านั้น ค่าที่คาดหวังของqคือความน่าจะเป็นที่ตำแหน่งอาร์เรย์ที่กำหนดจะไม่ถูกแตะต้องโดย ฟังก์ชันแฮช kฟังก์ชันสำหรับแต่ละรายการจากnรายการ ซึ่งคือ (ดังข้างต้น) ${\displaystyle 1-q}$${\displaystyle (1-q)^{k}}$

${\displaystyle E[q]=\left(1-{\frac {1}{m}}\right)^{kn}}$.

เป็นไปได้ที่จะพิสูจน์ได้โดยไม่ต้องมีสมมติฐานเรื่องความเป็นอิสระว่าqมีความเข้มข้นสูงมากรอบค่าที่คาดหวัง โดยเฉพาะอย่างยิ่งจากความไม่เท่าเทียมกันของ Azuma–Hoeffdingพวกเขาพิสูจน์ได้ว่า^{[ 8 ]}

${\displaystyle \Pr(\left|qE[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-2\lambda ^{2}/kn)}$

ด้วยเหตุนี้ เราจึงสามารถกล่าวได้ว่า ความน่าจะเป็นที่แน่นอนของผลบวกเท็จคือ

${\displaystyle \sum _{t}\Pr(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}$

เหมือนเดิม

จำนวนฟังก์ชันแฮชkต้องเป็นจำนวนเต็มบวก หากไม่คำนึงถึงข้อจำกัดนี้ สำหรับค่าmและnที่กำหนด ค่าkที่ทำให้ความน่าจะเป็นของผลบวกเท็จน้อยที่สุดคือ

${\displaystyle k={\frac {m}{n}}\ln 2.}$

จำนวนบิตที่ต้องการmเมื่อกำหนดn (จำนวนองค์ประกอบที่แทรก) และความน่าจะเป็นของผลบวกเท็จที่ต้องการε (และสมมติว่า ใช้ค่าk ที่เหมาะสมที่สุด) สามารถคำนวณได้โดยการแทนค่า k ที่เหมาะสมที่สุด ลงในนิพจน์ความน่าจะเป็นข้างต้น:

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac {m}{n}}\ln 2}=\left({\frac {1}{2}}\right)^{{\frac {m}{n}}\ln 2}}$

ซึ่งสามารถสรุปให้ง่ายขึ้นได้ดังนี้:

${\displaystyle \ln(\varepsilon )=-{\frac {m}{n}}\ln(2)^{2}.}$

ผลลัพธ์ที่ได้คือ:

${\displaystyle m=-{\frac {n\ln(\varepsilon )}{\ln(2)^{2}}}}$

ดังนั้นจำนวนบิตที่เหมาะสมที่สุดต่อองค์ประกอบคือ

${\displaystyle {\frac {m}{n}}=-{\frac {\ln(\varepsilon )}{\ln(2)^{2}}}\approx -2.08\ln(\varepsilon )}$

โดยใช้จำนวนฟังก์ชันแฮชk ที่สอดคล้องกัน (โดยไม่คำนึงถึงความเป็นจำนวนเต็ม):

${\displaystyle k=-{\frac {\ln(\varepsilon )}{\ln(2)}}.}$

ซึ่งหมายความว่าสำหรับความน่าจะเป็นบวกเท็จที่กำหนดεความยาวของตัวกรอง Bloom mจะเป็นสัดส่วนกับจำนวนองค์ประกอบที่ถูกกรองⁿและจำนวนฟังก์ชันแฮชที่ต้องการจะขึ้นอยู่กับความน่าจะเป็นบวกเท็จเป้าหมายε เท่านั้น [ ^{9 ]}

สูตรนี้เป็นค่าประมาณด้วยเหตุผลสามประการ ประการแรก และสำคัญน้อยที่สุด คือ มันประมาณค่าได้ เป็นซึ่งเป็นค่าประมาณเชิงอะซิมโทติกที่ดี (กล่าวคือ ซึ่งใช้ได้เมื่อm →∞) ประการที่สอง ซึ่งสำคัญกว่า คือ มันสมมติว่าในระหว่างการทดสอบความเป็นสมาชิก เหตุการณ์ที่บิตที่ทดสอบหนึ่งบิตถูกตั้งค่าเป็น 1 นั้นเป็นอิสระจากเหตุการณ์ที่บิตที่ทดสอบอื่น ๆ ถูกตั้งค่าเป็น 1 ประการที่สาม ซึ่งสำคัญที่สุด คือ มันสมมติว่าเป็นจำนวนเต็มโดยบังเอิญ ${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$${\displaystyle 1-{\frac {1}{m}}}$${\displaystyle e^{-{\frac {1}{m}}}}$${\displaystyle k={\frac {m}{n}}\ln 2}$

อย่างไรก็ตาม Goel และ Gupta ^{[ 10 ]}ให้ขอบเขตบนที่เข้มงวดซึ่งไม่มีการประมาณค่าและไม่ต้องการสมมติฐานใดๆ พวกเขาแสดงให้เห็นว่าความน่าจะเป็นบวกเท็จสำหรับตัวกรอง Bloom แบบจำกัดที่มีmบิต ( ), nองค์ประกอบ และkฟังก์ชันแฮชมีค่าสูงสุดเท่านั้น ${\displaystyle m>1}$

${\displaystyle \varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.}$

ขอบเขตนี้สามารถตีความได้ว่า สูตรโดยประมาณสามารถนำไปใช้ได้ โดยมีค่าปรับเพิ่มไม่เกินครึ่งหนึ่งของจำนวนองค์ประกอบ และค่าปรับลดไม่เกินหนึ่งบิต ${\displaystyle \left(1-e^{-{\frac {kn}{m}}}\right)^{k}}$

จำนวนองค์ประกอบใน Bloom filter สามารถประมาณได้โดยใช้สูตรต่อไปนี้

${\displaystyle n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],}$

โดยที่เป็นการประมาณจำนวนรายการในตัวกรองmคือความยาว (ขนาด) ของตัวกรองkคือจำนวนฟังก์ชันแฮช และXคือจำนวนบิตที่ตั้งค่าเป็นหนึ่ง^{[ 11 ]}${\displaystyle n^{*}}$

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

${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]}$

และ

${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].}$

สามารถประมาณขนาดของสหภาพของพวกเขาได้ดังนี้

${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m}}\right],}$

โดยที่จำนวนบิตที่ตั้งค่าเป็นหนึ่งในตัวกรอง Bloom ทั้งสองตัวนั้นคือเท่าใด สุดท้ายแล้ว สามารถประมาณค่าส่วนที่ทับซ้อนกันได้ดังนี้ ${\displaystyle n(A\cup B)}$

${\displaystyle n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),}$

โดยใช้สูตรทั้งสามร่วมกัน^{[ 11 ]}

• แตกต่างจาก ตารางแฮชมาตรฐานที่ใช้การกำหนดแอดเดรสแบบเปิดสำหรับการแก้ไขการชนกันตัวกรอง Bloom ที่มีขนาดคงที่สามารถแทนชุดข้อมูลที่มีจำนวนองค์ประกอบมากเท่าใดก็ได้ การเพิ่มองค์ประกอบจะไม่ล้มเหลวเนื่องจากโครงสร้างข้อมูล "เต็ม" อย่างไรก็ตาม อัตราผลลัพธ์ที่ผิดพลาดจะเพิ่มขึ้นเรื่อยๆ เมื่อมีการเพิ่มองค์ประกอบจนกระทั่งบิตทั้งหมดในตัวกรองถูกตั้งค่าเป็น 1 ซึ่ง ณ จุดนั้น การค้นหา ทั้งหมดจะให้ผลลัพธ์ที่เป็นบวก ในขณะที่การแฮชแบบกำหนดแอดเดรสแบบเปิดจะไม่เกิดผลลัพธ์ที่ผิดพลาด แต่ประสิทธิภาพจะลดลงเรื่อยๆ จนเข้าใกล้การค้นหาเชิงเส้น
• การรวมและการหาจุดตัดของ Bloom filter ที่มีขนาดและชุดฟังก์ชันแฮชเดียวกัน สามารถทำได้โดยใช้ การดำเนินการ OR และ AND ระดับบิตตามลำดับ การดำเนินการรวม Bloom filter นั้นไม่สูญเสียข้อมูลในแง่ที่ว่า Bloom filter ที่ได้จะเหมือนกับ Bloom filter ที่สร้างขึ้นใหม่โดยใช้การรวมกันของสองชุด การดำเนินการหาจุดตัดนั้นมีคุณสมบัติที่อ่อนกว่า กล่าวคือ ความน่าจะเป็นของผลบวกเท็จใน Bloom filter ที่ได้จะมีค่าสูงสุดเท่ากับความน่าจะเป็นของผลบวกเท็จใน Bloom filter ที่เป็นส่วนประกอบตัวใดตัวหนึ่ง แต่ค่าอาจมากกว่าความน่าจะเป็นของผลบวกเท็จใน Bloom filter ที่สร้างขึ้นใหม่โดยใช้การหาจุดตัดของสองชุด
• รหัสซ้อนทับบางประเภทสามารถมองได้ว่าเป็นตัวกรอง Bloom ที่นำมาใช้กับการ์ดที่มีรอยบากที่ ขอบ ตัวอย่างเช่นZatocodingซึ่งคิดค้นโดยCalvin Mooersในปี 1947 โดยชุดของหมวดหมู่ที่เกี่ยวข้องกับข้อมูลชิ้นหนึ่งจะถูกแทนด้วยรอยบากบนการ์ด โดยมีรูปแบบสุ่มของรอยบากสี่รอยสำหรับแต่ละหมวดหมู่

• แมลงวันผลไม้ใช้ตัวกรอง Bloom เวอร์ชันดัดแปลงเพื่อตรวจจับกลิ่นแปลกใหม่ โดยมีคุณสมบัติเพิ่มเติม ได้แก่ ความคล้ายคลึงของกลิ่นแปลกใหม่กับกลิ่นตัวอย่างที่เคยพบมาก่อน และระยะเวลาที่ผ่านไปนับตั้งแต่เคยได้กลิ่นเดียวกันมาก่อน^{[ 12 ]}
• เซิร์ฟเวอร์ของAkamai Technologiesซึ่งเป็น ผู้ให้บริการ ส่งมอบเนื้อหาใช้ Bloom filter เพื่อป้องกันไม่ให้ "one-hit-wonders" ถูกจัดเก็บในแคชดิสก์ One-hit-wonders คือวัตถุเว็บที่ผู้ใช้ร้องขอเพียงครั้งเดียว ซึ่ง Akamai พบว่ามีการนำไปใช้กับโครงสร้างพื้นฐานการแคชเกือบสามในสี่ การใช้ Bloom filter เพื่อตรวจจับการร้องขอครั้งที่สองสำหรับวัตถุเว็บและแคชวัตถุนั้นเฉพาะในการร้องขอครั้งที่สองเท่านั้น จะช่วยป้องกันไม่ให้ one-hit wonders เข้าสู่แคชดิสก์ ลดภาระงานของดิสก์ลงอย่างมากและเพิ่มอัตราการเข้าถึงแคชดิสก์^{[ 13 ]}
• Google Bigtable , Apache HBase , Apache Cassandra , ScyllaDBและPostgreSQL ^{[ 14 ]}ใช้ Bloom filters เพื่อลดการค้นหาข้อมูลในดิสก์สำหรับแถวหรือคอลัมน์ที่ไม่มีอยู่จริง การหลีกเลี่ยงการค้นหาข้อมูลในดิสก์ที่มีค่าใช้จ่ายสูงจะช่วยเพิ่มประสิทธิภาพการทำงานของการสืบค้นฐานข้อมูลได้อย่างมาก^{[ 15 ]}
• ก่อนหน้านี้ เว็บเบราว์เซอร์Google Chrome ใช้ Bloom filter เพื่อระบุURL ที่เป็นอันตราย URL ใดๆ จะถูกตรวจสอบกับ Bloom filter ในเครื่องก่อน และหาก Bloom filter ให้ผลลัพธ์เป็นบวกเท่านั้น จึงจะทำการตรวจสอบ URL อย่างละเอียด (และผู้ใช้จะได้รับการแจ้งเตือน หากผลการตรวจสอบเป็นบวกเช่นกัน) ^{[ 16 ] [ 17 ]}
• Mozilla Firefoxใช้ตัวกรอง Bloom แบบเรียงลำดับสำหรับการเพิกถอนใบรับรอง^{[ 18 ] [ 19 ]}และสำหรับการบล็อกส่วนเสริมที่เป็นอันตราย^{[ 20 ]}
• Microsoft Bing (เครื่องมือค้นหา)ใช้ตัวกรอง Bloom แบบลำดับชั้นหลายระดับสำหรับดัชนีการค้นหาBitFunnelตัวกรอง Bloom ให้ต้นทุนที่ต่ำกว่าดัชนี Bing รุ่นก่อนหน้าซึ่งใช้ไฟล์แบบกลับด้าน^{[ 21 ]}
• แคชพร็อกซีเว็บSquid ใช้ตัวกรอง Bloom สำหรับไดเจสต์แคช^{[ 22 ]}
• Bitcoinใช้ Bloom filters เพื่อเร่งความเร็วในการซิงโครไนซ์กระเป๋าเงินจนกระทั่งมีการค้นพบช่องโหว่ด้านความเป็นส่วนตัวในการใช้งาน Bloom filters ^{[ 23 ]}
• ระบบ จัดเก็บข้อมูลแบบถาวร Ventiใช้ตัวกรอง Bloom เพื่อตรวจจับข้อมูลที่จัดเก็บไว้ก่อนหน้านี้^{[ 24 ]}
• ตัวตรวจสอบโมเดล SPINใช้ตัวกรอง Bloom เพื่อติดตามพื้นที่สถานะที่เข้าถึงได้สำหรับปัญหาการตรวจสอบขนาดใหญ่^{[ 25 ]}
• กรอบ งานวิเคราะห์ แบบเรียงลำดับใช้ตัวกรอง Bloom เพื่อเร่งความเร็วการเชื่อมต่อแบบไม่สมมาตร โดยที่ชุดข้อมูลที่เชื่อมต่อชุดหนึ่งมีขนาดใหญ่กว่าอีกชุดหนึ่งอย่างมาก (มักเรียกว่าการเชื่อมต่อ Bloom ในเอกสารเกี่ยวกับฐานข้อมูล) ^{[ 26 ]}
• ตัวแทน รับส่งจดหมาย (MTA) ของ Eximใช้ตัวกรอง Bloom ในคุณสมบัติการจำกัดอัตราการรับส่งข้อมูล
• Mediumใช้ Bloom filters เพื่อหลีกเลี่ยงการแนะนำบทความที่ผู้ใช้เคยอ่านมาก่อน^{[ 27 ]}
• Ethereum ใช้ Bloom filter เพื่อค้นหาบันทึก (log) บน บล็อกเชน Ethereum ได้อย่างรวดเร็ว
• Grafana Tempo ใช้ Bloom filters เพื่อปรับปรุงประสิทธิภาพการค้นหาโดยการจัดเก็บ bloom filters สำหรับแต่ละบล็อกแบ็กเอนด์ ซึ่งจะถูกเข้าถึงในแต่ละการค้นหาเพื่อกำหนดบล็อกที่มีข้อมูลที่ตรงตามเกณฑ์การค้นหาที่ให้มา^{[ 28 ]}

ตัวกรอง Bloom แบบคลาสสิกใช้พื้นที่บิตต่อคีย์ที่แทรกเข้าไป โดยที่คืออัตราการเกิดผลบวกเท็จของตัวกรอง Bloom อย่างไรก็ตาม พื้นที่ที่จำเป็นอย่างแท้จริงสำหรับโครงสร้างข้อมูลใดๆ ที่ทำหน้าที่เหมือนกับตัวกรอง Bloom นั้นมีเพียงต่อคีย์ เท่านั้น ^{[ 29 ]}ดังนั้น ตัวกรอง Bloom จึงใช้พื้นที่มากกว่าโครงสร้างข้อมูลที่เหมาะสมเทียบเท่าถึง 44% ${\displaystyle 1.44\log _{2}(1/\varepsilon )}$${\displaystyle \varepsilon }$${\displaystyle \log _{2}(1/\varepsilon )}$

Pagh และคณะได้นำเสนอโครงสร้างข้อมูลที่ใช้บิตในขณะที่รองรับการดำเนินการที่มีเวลาเฉลี่ยคงที่^{[ 30 ]}โครงสร้างข้อมูลของพวกเขาส่วนใหญ่เป็นเชิงทฤษฎี แต่มีความเกี่ยวข้องอย่างใกล้ชิดกับตัวกรองผลหาร ที่ใช้กันอย่างแพร่หลาย ซึ่งสามารถกำหนดพารามิเตอร์เพื่อใช้บิตของพื้นที่สำหรับพารามิเตอร์ใดๆในขณะที่รองรับการดำเนินการที่มีเวลา^{[ 31 ]}ข้อดีของตัวกรองผลหาร เมื่อเปรียบเทียบกับตัวกรอง Bloom ได้แก่ความเป็นท้องถิ่นของการอ้างอิงและความสามารถในการรองรับการลบ ${\textstyle (1+o(1))n\log _{2}(1/\epsilon )+O(n)}$${\displaystyle (1+\delta )n\log \epsilon ^{-1}+3n}$${\displaystyle \delta >0}$${\displaystyle O(\delta ^{-2})}$

อีกทางเลือกหนึ่งนอกเหนือจากตัวกรอง Bloom แบบคลาสสิกคือตัวกรอง Cuckooซึ่งใช้รูปแบบที่มีประสิทธิภาพด้านพื้นที่ของCuckoo Hashingในกรณีนี้ จะมีการสร้างตารางแฮชขึ้น ซึ่งไม่ได้เก็บทั้งคีย์หรือค่า แต่จะเก็บลายนิ้วมือสั้นๆ (แฮชขนาดเล็ก) ของคีย์ หากการค้นหาคีย์พบลายนิ้วมือที่ตรงกัน แสดงว่าคีย์นั้นน่าจะอยู่ในชุด ตัวกรอง Cuckoo รองรับการลบและมีตำแหน่งอ้างอิง ที่ดี กว่าตัวกรอง Bloom ^{[ 32 ]}นอกจากนี้ ในบางช่วงพารามิเตอร์ ตัวกรอง Cuckoo สามารถกำหนดพารามิเตอร์เพื่อให้การรับประกันพื้นที่ที่เกือบจะเหมาะสมที่สุดได้^{[ 32 ]}

ทางเลือกมากมายสำหรับตัวกรอง Bloom รวมถึงตัวกรองผลหารและตัวกรองนกกาเหว่าล้วนมีพื้นฐานมาจากแนวคิดของการแฮชคีย์เป็นลายนิ้วมือแบบสุ่ม 2 บิต จากนั้นจึงจัดเก็บลายนิ้วมือเหล่านั้นไว้ในตารางแฮชขนาดกะทัดรัด เทคนิคนี้ซึ่งนำเสนอครั้งแรกโดย Carter et al. ในปี 1978 ^{[ 29 ]}อาศัยข้อเท็จจริงที่ว่าตารางแฮชขนาดกะทัดรัดสามารถนำไปใช้งานโดยใช้พื้นที่น้อยกว่าตารางแฮชที่ไม่กะทัดรัดประมาณ 2 บิต การใช้ ตารางแฮช แบบกระชับสามารถลดการใช้พื้นที่ลงได้เพียง2 บิต^{[ 33 ]}ในขณะที่ยังคงรองรับการดำเนินการแบบคงที่ในพารามิเตอร์ที่หลากหลาย ${\displaystyle (\log n+\log \epsilon ^{-1})}$${\displaystyle n\log n}$${\displaystyle n\log _{2}(e/\epsilon )+o(n)}$

Putze, Sanders และ Singler (2007)ได้ศึกษา Bloom filter รูปแบบต่างๆ ที่เร็วกว่าหรือใช้พื้นที่น้อยกว่า Bloom filter แบบคลาสสิก แนวคิดพื้นฐานของรูปแบบที่เร็วขึ้นคือการจัดเก็บค่าแฮช k ค่าที่เกี่ยวข้องกับแต่ละคีย์ไว้ในบล็อกหนึ่งหรือสองบล็อกที่มีขนาดเท่ากับบล็อกแคชหน่วยความจำของโปรเซสเซอร์ (โดยปกติคือ 64 ไบต์) ซึ่งคาดว่าจะช่วยปรับปรุงประสิทธิภาพโดยลดจำนวนการพลาดแคชหน่วย ความจำที่อาจเกิดขึ้นได้ อย่างไรก็ตาม รูปแบบที่เสนอมานี้มีข้อเสียคือใช้พื้นที่มากกว่า Bloom filter แบบคลาสสิกประมาณ 32%

วิธีการที่ประหยัดพื้นที่นี้อาศัยการใช้ฟังก์ชันแฮชเพียงฟังก์ชันเดียวที่สร้างค่าสำหรับแต่ละคีย์ในช่วงที่ กำหนด โดยที่คืออัตราการตรวจจับผิดพลาดที่ต้องการ จากนั้นลำดับของค่าจะถูกจัดเรียงและบีบอัดโดยใช้การเข้ารหัสแบบ Golomb (หรือเทคนิคการบีบอัดอื่นๆ) เพื่อใช้พื้นที่ใกล้เคียงกับบิต ในการค้นหาข้อมูลใน Bloom filter สำหรับคีย์ที่กำหนด ก็เพียงพอที่จะตรวจสอบว่าค่าที่ตรงกันนั้นถูกเก็บไว้ใน Bloom filter หรือไม่ การคลายการบีบอัด Bloom filter ทั้งหมดสำหรับทุกการค้นหาจะทำให้วิธีการนี้ใช้งานไม่ได้เลย เพื่อแก้ปัญหานี้ ลำดับของค่าจะถูกแบ่งออกเป็นบล็อกขนาดเล็กที่มีขนาดเท่ากันและบีบอัดแยกกัน ในเวลาค้นหา จะต้องคลายการบีบอัดเพียงครึ่งบล็อกโดยเฉลี่ยเท่านั้น เนื่องจากค่าใช้จ่ายในการคลายการบีบอัด วิธีการนี้อาจช้ากว่า Bloom filter แบบคลาสสิก แต่สิ่งนี้อาจได้รับการชดเชยด้วยข้อเท็จจริงที่ว่าต้องคำนวณฟังก์ชันแฮชเพียงฟังก์ชันเดียว ${\displaystyle \left[0,n/\varepsilon \right]}$${\displaystyle \varepsilon }$${\displaystyle n\log _{2}(1/\varepsilon )}$

Graf & Lemire (2020)อธิบายถึงวิธีการที่เรียกว่าตัวกรองแบบ XOR โดยที่พวกเขาจัดเก็บลายนิ้วมือไว้ในตาราง แฮชที่สมบูรณ์แบบชนิดพิเศษทำให้ได้ตัวกรองที่มีประสิทธิภาพด้านหน่วยความจำมากกว่า ( บิตต่อคีย์) และเร็วกว่าตัวกรอง Bloom หรือตัวกรอง Cuckoo (การประหยัดเวลามาจากการที่การค้นหาต้องใช้การเข้าถึงหน่วยความจำเพียงสามครั้ง ซึ่งสามารถดำเนินการพร้อมกันได้) อย่างไรก็ตาม การสร้างตัวกรองนั้นซับซ้อนกว่าตัวกรอง Bloom และตัวกรอง Cuckoo และไม่สามารถแก้ไขชุดข้อมูลหลังจากสร้างเสร็จแล้วได้ ${\displaystyle 1.23\log _{2}(1/\varepsilon )}$

มี Bloom filters มากกว่า 60 รูปแบบ มีการสำรวจสาขานี้มากมาย และมีการพัฒนาแอปพลิเคชันอย่างต่อเนื่อง (ดูเช่น Luo และคณะ^{[ 34 ]} ) บางรูปแบบแตกต่างจากข้อเสนอเดิมมากพอที่จะถือเป็นการละเมิดหรือแยกย่อยจากโครงสร้างข้อมูลเดิมและปรัชญา^{[ 34 ]} ยังไม่มี การดำเนินการใด ๆ ที่รวม Bloom filters เข้ากับงานอื่น ๆ เกี่ยวกับการฉายภาพแบบสุ่มการรับรู้แบบบีบอัดและการแฮชที่ไวต่อตำแหน่ง (แม้ว่า Dasgupta และคณะ^{[ 35 ]}จะเป็นความพยายามหนึ่งที่ได้รับแรงบันดาลใจจากประสาทวิทยาศาสตร์)

เครือข่ายการส่งเนื้อหา (Content Delivery Network หรือ CDN) ทั่วโลก ใช้แคชเว็บเพื่อแคชและให้บริการเนื้อหาเว็บแก่ผู้ใช้ด้วยประสิทธิภาพและความน่าเชื่อถือที่ดียิ่งขึ้น แอปพลิเคชันสำคัญอย่างหนึ่งของ Bloom filter คือการใช้ในการกำหนดอย่างมีประสิทธิภาพว่าควรจัดเก็บวัตถุเว็บใดไว้ในแคชเว็บเหล่านี้ เกือบสามในสี่ของ URL ที่เข้าถึงจากแคชเว็บทั่วไปเป็น "one-hit-wonders" ซึ่งผู้ใช้เข้าถึงเพียงครั้งเดียวและไม่เข้าถึงอีกเลย การจัดเก็บ one-hit-wonders ในแคชเว็บเป็นการสิ้นเปลืองทรัพยากรดิสก์อย่างชัดเจน เนื่องจากจะไม่ถูกเข้าถึงอีกเลย เพื่อป้องกันการแคช one-hit-wonders จึงใช้ Bloom filter ในการติดตาม URL ทั้งหมดที่ผู้ใช้เข้าถึง วัตถุเว็บจะถูกแคชก็ต่อเมื่อมีการเข้าถึงอย่างน้อยหนึ่งครั้งก่อนหน้านี้ กล่าวคือ วัตถุจะถูกแคชในการร้องขอครั้งที่สอง การใช้ Bloom filter ในลักษณะนี้ช่วยลดภาระงานการเขียนลงดิสก์ได้อย่างมาก เนื่องจาก one-hit-wonders ส่วนใหญ่จะไม่ถูกเขียนลงในแคชดิสก์ นอกจากนี้ การกรอง one-hit-wonders ออกยังช่วยประหยัดพื้นที่แคชบนดิสก์ ทำให้เพิ่มอัตราการเข้าถึงแคช (cache hit rate) ได้อีกด้วย^{[ 13 ]}

Kiss และคณะได้อธิบายโครงสร้างใหม่สำหรับตัวกรอง Bloom ที่หลีกเลี่ยงผลบวกเท็จ นอกเหนือจากการไม่มีผลลบเท็จตามปกติ^{[ 36 ]}โครงสร้างนี้ใช้กับเอกภพที่มีขอบเขตจำกัดซึ่งจะนำองค์ประกอบของเซตมาใช้ โดยอาศัยรูปแบบการทดสอบกลุ่ม เชิงผสมที่ไม่ปรับตัวที่มีอยู่แล้ว โดย Eppstein, Goodrich และ Hirschberg แตกต่างจากตัวกรอง Bloom ทั่วไป องค์ประกอบจะถูกแฮชไปยังอาร์เรย์บิตผ่านฟังก์ชันที่กำหนดได้ รวดเร็ว และคำนวณได้ง่าย ขนาดเซตสูงสุดที่หลีกเลี่ยงผลบวกเท็จได้อย่างสมบูรณ์เป็นฟังก์ชันของขนาดเอกภพและถูกควบคุมโดยปริมาณหน่วยความจำที่จัดสรร

อีกทางเลือกหนึ่งคือ สามารถสร้าง Bloom filter เริ่มต้นได้ด้วยวิธีมาตรฐาน จากนั้น ด้วยโดเมนที่มีขอบเขตจำกัดและสามารถแจงนับได้ จะสามารถค้นหาผลบวกเท็จทั้งหมดได้อย่างละเอียดถี่ถ้วน แล้วจึงสร้าง Bloom filter ตัวที่สองจากรายการนั้น ผลบวกเท็จในฟิลเตอร์ตัวที่สองจะได้รับการจัดการในทำนองเดียวกันโดยการสร้างตัวที่สาม และต่อไปเรื่อยๆ เนื่องจากเอกภพมีขอบเขตจำกัดและชุดของผลบวกเท็จจะลดลงอย่างเคร่งครัดในแต่ละขั้นตอน กระบวนการนี้จึงส่งผลให้เกิด Bloom filter แบบ เรียงลำดับ ที่มีขอบเขตจำกัด ซึ่ง (บนโดเมนที่ปิดและมีขอบเขตจำกัดนี้) จะสร้างเฉพาะผลบวกจริงและผลลบจริงเท่านั้น ในการตรวจสอบการเป็นสมาชิกในฟิลเตอร์แบบเรียงลำดับ จะมีการสอบถามฟิลเตอร์เริ่มต้น และหากผลลัพธ์เป็นบวก จะมีการสอบถามฟิลเตอร์ตัวที่สอง และต่อไปเรื่อยๆ โครงสร้างนี้ใช้ในCRLite ซึ่งเป็นกลไกการกระจาย สถานะการเพิกถอนใบรับรองที่เสนอสำหรับWeb PKIและCertificate Transparencyถูกนำมาใช้เพื่อปิดชุดของใบรับรองที่มีอยู่^{[ 37 ]}

ตัวกรองแบบนับ (Counting filters) เป็นวิธีการหนึ่งในการดำเนิน การ ลบข้อมูลในตัวกรอง Bloom โดยไม่ต้องสร้างตัวกรองขึ้นใหม่ ในตัวกรองแบบนับ ตำแหน่งของอาร์เรย์ (buckets) จะถูกขยายจากบิตเดียวไปเป็นตัวนับแบบหลายบิต อันที่จริง ตัวกรอง Bloom ทั่วไปสามารถพิจารณาได้ว่าเป็นตัวกรองแบบนับที่มีขนาด bucket หนึ่งบิต ตัวกรองแบบนับนี้ได้รับการแนะนำโดยFan et al. (2000 )

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

ปัญหาการล้นค่าทางคณิตศาสตร์ของถังเก็บค่าเป็นปัญหาหนึ่ง และถังเก็บค่าควรมีขนาดใหญ่พอที่จะทำให้ปัญหานี้เกิดขึ้นได้ยาก หากเกิดขึ้นแล้ว การเพิ่มและลดค่าจะต้องทำให้ค่าในถังเก็บค่าคงอยู่ที่ค่าสูงสุดที่เป็นไปได้ เพื่อรักษาคุณสมบัติของตัวกรอง Bloom ไว้

โดยทั่วไปขนาดของตัวนับจะมีขนาด 3 หรือ 4 บิต ดังนั้นตัวกรอง Bloom แบบนับจึงใช้พื้นที่มากกว่าตัวกรอง Bloom แบบคงที่ถึง 3 ถึง 4 เท่า ในทางตรงกันข้าม โครงสร้างข้อมูลของPagh, Pagh & Rao (2005)และFan et al. (2014)ยังอนุญาตให้ลบข้อมูลได้ แต่ใช้พื้นที่น้อยกว่าตัวกรอง Bloom แบบคงที่

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

Bonomi et al. (2006)ได้นำเสนอโครงสร้างข้อมูลที่ใช้การแฮชแบบ d-left ซึ่งมีฟังก์ชันการทำงานเทียบเท่ากัน แต่ใช้พื้นที่ประมาณครึ่งหนึ่งของการนับ Bloom filter ปัญหาเรื่องความสามารถในการขยายขนาดจะไม่เกิดขึ้นในโครงสร้างข้อมูลนี้ เมื่อความจุที่ออกแบบไว้เกินขีดจำกัดแล้ว คีย์ต่างๆ สามารถแทรกกลับเข้าไปในตารางแฮชใหม่ที่มีขนาดเป็นสองเท่าได้

รูปแบบที่มีประสิทธิภาพด้านพื้นที่จัดเก็บข้อมูลโดยPutze, Sanders & Singler (2007)สามารถนำมาใช้ในการสร้างตัวกรองการนับโดยรองรับการแทรกและการลบได้เช่นกัน

Rottenstreich, Kanizo และ Keslassy (2012)ได้นำเสนอวิธีการทั่วไปใหม่ที่อิงตามการเพิ่มค่าตัวแปร ซึ่งช่วยปรับปรุงโอกาสการเกิดผลบวกเท็จของการนับ Bloom filter และรูปแบบต่างๆ ได้อย่างมีนัยสำคัญ ในขณะที่ยังคงรองรับการลบอยู่ แตกต่างจากการนับ Bloom filter ตรงที่ ในแต่ละการแทรกองค์ประกอบ ค่าแฮชของตัวนับจะเพิ่มขึ้นด้วยค่าตัวแปรแฮชแทนที่จะเป็นการเพิ่มค่าแบบหน่วย ในการสอบถามองค์ประกอบ จะพิจารณาค่าที่แน่นอนของตัวนับ ไม่ใช่แค่ค่าบวกเท่านั้น หากผลรวมที่แสดงโดยค่าตัวนับไม่สามารถประกอบขึ้นจากค่าตัวแปรที่สอดคล้องกันสำหรับองค์ประกอบที่สอบถามได้ คำตอบเชิงลบอาจถูกส่งคืนไปยังการสอบถามนั้น

Kim et al. (2019)แสดงให้เห็นว่าผลบวกเท็จของตัวกรอง Counting Bloom ลดลงจาก k=1 ไปจนถึงจุดที่กำหนดและเพิ่มขึ้นจาก ไปจนถึงค่าอนันต์บวก และพบว่าเป็นฟังก์ชันของเกณฑ์การนับ^{[ 38 ]}${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$

ตัวกรอง Bloom สามารถจัดระเบียบในโครงสร้างข้อมูล แบบกระจาย เพื่อดำเนินการคำนวณฟังก์ชันรวมแบบ กระจายศูนย์อย่างสมบูรณ์ การ รวมแบบกระจายศูนย์ทำให้การวัดแบบรวมศูนย์พร้อมใช้งานในแต่ละโหนดของเครือข่ายแบบกระจายศูนย์โดยไม่ต้องมีหน่วยงานคำนวณส่วนกลางเพื่อจุดประสงค์นี้^{[ 39 ]}

ตัวกรอง Bloom แบบขนานสามารถนำไปใช้เพื่อใช้ประโยชน์จากหน่วยประมวล ผลหลายตัว (PE) ที่มีอยู่ในเครื่องแบบขนานที่ไม่มีการแชร์ทรัพยากรอุปสรรคสำคัญประการหนึ่งสำหรับตัวกรอง Bloom แบบขนานคือการจัดระเบียบและการสื่อสารข้อมูลที่ไม่มีลำดับ ซึ่งโดยทั่วไปจะกระจายอย่างสม่ำเสมอทั่ว PE ทั้งหมดเมื่อเริ่มต้นหรือเมื่อแทรกเป็นชุด เพื่อจัดลำดับข้อมูล สามารถใช้วิธีการสองวิธี ได้แก่ การใช้ตัวกรอง Bloom กับข้อมูลทั้งหมดที่จัดเก็บไว้บน PE แต่ละตัว เรียกว่าตัวกรอง Bloom แบบจำลอง หรือการแบ่งตัวกรอง Bloom กับข้อมูลทั้งหมดออกเป็นส่วนเท่าๆ กัน โดยแต่ละ PE จะจัดเก็บส่วนหนึ่งไว้^{[ 40 ]}สำหรับทั้งสองวิธี จะใช้ตัวกรอง Bloom แบบ "Single Shot" ซึ่งคำนวณแฮชเพียงครั้งเดียว ส่งผลให้บิตพลิกกลับหนึ่งบิตต่อองค์ประกอบ เพื่อลดปริมาณการสื่อสาร

ตัวกรอง Bloom แบบกระจายเริ่มต้นด้วยการแฮชองค์ประกอบทั้งหมดใน PE ท้องถิ่นก่อน จากนั้นจึงเรียงลำดับตามค่าแฮชในเครื่องนั้นๆ ซึ่งสามารถทำได้ในเวลาเชิงเส้นโดยใช้เช่นBucket sortและยังช่วยให้ตรวจจับข้อมูลซ้ำในเครื่องได้ด้วย การเรียงลำดับใช้เพื่อจัดกลุ่มค่าแฮชโดยใช้ PE ที่กำหนดเป็นตัวคั่นเพื่อสร้างตัวกรอง Bloom สำหรับแต่ละกลุ่ม หลังจากเข้ารหัสตัวกรอง Bloom เหล่านี้โดยใช้เช่นGolomb codingแล้ว ตัวกรอง Bloom แต่ละตัวจะถูกส่งเป็นแพ็กเก็ตไปยัง PE ที่รับผิดชอบค่าแฮชที่ถูกแทรกเข้าไป PE p รับผิดชอบค่าแฮชทั้งหมดระหว่างค่าและโดยที่ s คือขนาดทั้งหมดของตัวกรอง Bloom เหนือข้อมูลทั้งหมด เนื่องจากแต่ละองค์ประกอบจะถูกแฮชเพียงครั้งเดียว ดังนั้นจึงมีการตั้งค่าเพียงบิตเดียว ในการตรวจสอบว่าองค์ประกอบถูกแทรกเข้าไปในตัวกรอง Bloom หรือไม่ จำเป็นต้องดำเนินการเฉพาะกับ PE ที่รับผิดชอบค่าแฮชขององค์ประกอบนั้นเท่านั้น การดำเนินการแทรกเพียงครั้งเดียวสามารถทำได้อย่างมีประสิทธิภาพเช่นกัน เนื่องจากต้องเปลี่ยนตัวกรอง Bloom ของ PE เพียงเครื่องเดียวเท่านั้น เมื่อเทียบกับตัวกรอง Bloom แบบจำลองที่ PE ทุกเครื่องจะต้องอัปเดตตัวกรอง Bloom ของตนเอง ด้วยการกระจายตัวกรอง Bloom ทั่วโลกไปทั่ว PE ทั้งหมดแทนที่จะจัดเก็บแยกกันในแต่ละ PE ขนาดของตัวกรอง Bloom จึงสามารถใหญ่ขึ้นได้มาก ส่งผลให้มีความจุมากขึ้นและอัตราการเกิดผลบวกเท็จต่ำลง ตัวกรอง Bloom แบบกระจายสามารถใช้เพื่อปรับปรุงอัลกอริธึมการตรวจจับรายการซ้ำ^{[ 41 ]}โดยการกรององค์ประกอบที่ 'ไม่ซ้ำกัน' มากที่สุด ซึ่งสามารถคำนวณได้โดยการสื่อสารเฉพาะแฮชขององค์ประกอบ ไม่ใช่ตัวองค์ประกอบเองซึ่งมีปริมาณมากกว่ามาก และลบออกจากชุด ลดภาระงานสำหรับอัลกอริธึมการตรวจจับรายการซ้ำที่ใช้ในภายหลัง ${\displaystyle p*(s/|{\text{PE}}|)}$${\displaystyle (p+1)*(s/|{\text{PE}}|)}$

ในระหว่างการสื่อสารของแฮช PE จะค้นหาบิตที่ถูกตั้งค่าในแพ็กเก็ตที่รับมากกว่าหนึ่งแพ็กเก็ต เนื่องจากนั่นหมายความว่าองค์ประกอบสองรายการมีแฮชเดียวกันและอาจเป็นรายการซ้ำ หากเกิดกรณีนี้ ข้อความที่มีดัชนีของบิต ซึ่งเป็นแฮชขององค์ประกอบที่อาจเป็นรายการซ้ำ จะถูกส่งไปยัง PE ที่ส่งแพ็กเก็ตที่มีบิตที่ตั้งค่าไว้ หากผู้ส่งรายเดียวส่งดัชนีหลายรายการไปยัง PE เดียวกัน การเข้ารหัสดัชนีก็อาจเป็นประโยชน์เช่นกัน องค์ประกอบทั้งหมดที่ไม่ได้ส่งแฮชกลับมาจะรับประกันได้ว่าไม่ใช่รายการซ้ำและจะไม่ถูกประเมินต่อไป สำหรับองค์ประกอบที่เหลือ สามารถใช้อัลกอริทึมการแบ่งพาร์ติชันใหม่^{[ 42 ]}ได้ ก่อนอื่น องค์ประกอบทั้งหมดที่มีค่าแฮชส่งกลับมาจะถูกส่งไปยัง PE ที่รับผิดชอบแฮชขององค์ประกอบนั้น องค์ประกอบใดๆ และรายการซ้ำขององค์ประกอบนั้นจะได้รับการรับประกันว่าจะอยู่ใน PE เดียวกัน ในขั้นตอนที่สอง PE แต่ละตัวจะใช้อัลกอริธึมแบบลำดับสำหรับการตรวจจับข้อมูลซ้ำในองค์ประกอบที่ได้รับ ซึ่งมีจำนวนเพียงเศษเสี้ยวของจำนวนองค์ประกอบเริ่มต้น การอนุญาตให้มีอัตราการตรวจจับผิดพลาดสำหรับข้อมูลซ้ำจะช่วยลดปริมาณการสื่อสารลงได้อีก เนื่องจาก PE ไม่จำเป็นต้องส่งองค์ประกอบที่มีแฮชซ้ำกันเลย แต่สามารถทำเครื่องหมายองค์ประกอบใดๆ ที่มีแฮชซ้ำว่าเป็นข้อมูลซ้ำได้ ดังนั้น อัตราการตรวจจับผิดพลาดสำหรับข้อมูลซ้ำจึงเท่ากับอัตราการตรวจจับผิดพลาดของตัวกรอง Bloom ที่ใช้

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

การจำลอง Bloom filtersจะจัดระเบียบข้อมูลโดยใช้ อัลกอริทึม ไฮเปอร์คิว บ์ที่รู้จักกันดี สำหรับการกระจายข่าว เช่น^{[ 43 ]}ก่อนอื่น PE แต่ละตัวจะคำนวณ Bloom filter เหนือองค์ประกอบท้องถิ่นทั้งหมดและจัดเก็บไว้ โดยการทำซ้ำลูปที่ในแต่ละขั้นตอน i PE จะส่ง Bloom filter ท้องถิ่นของตนเหนือมิติ i และรวม Bloom filter ที่ได้รับเหนือมิติเข้ากับ Bloom filter ท้องถิ่นของตน ทำให้สามารถเพิ่มจำนวนองค์ประกอบที่ Bloom filter แต่ละตัวมีเป็นสองเท่าในแต่ละรอบได้ หลังจากส่งและรับ Bloom filter เหนือทุกมิติแล้ว PE แต่ละตัวจะมี Bloom filter ทั่วโลกเหนือองค์ประกอบทั้งหมด ${\displaystyle \log |{\text{PE}}|}$

การจำลอง Bloom filter จะมีประสิทธิภาพมากกว่าเมื่อจำนวนคำค้นหามากกว่าจำนวนองค์ประกอบที่ Bloom filter มีอยู่มาก จุดคุ้มทุนเมื่อเทียบกับ Bloom filter แบบกระจายจะอยู่ที่ประมาณหลังจากการเข้าถึง โดยมีอัตราการเกิดผลบวกเท็จของ Bloom filter เป็น ${\displaystyle |{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$${\displaystyle f^{\text{+}}}$

ตัวกรอง Bloom สามารถใช้สำหรับการซิงโครไนซ์ข้อมูล โดยประมาณได้ ดังเช่นในByers et al. (2004)ตัวกรอง Bloom แบบนับจำนวนสามารถใช้เพื่อประมาณจำนวนความแตกต่างระหว่างสองชุด และวิธีการนี้ได้อธิบายไว้ในAgarwal & Trachtenberg (2006 )

ตัวกรอง Bloom สามารถปรับให้เข้ากับบริบทของข้อมูลสตรีมมิ่งได้ ตัวอย่างเช่นDeng & Rafiei (2006)เสนอตัวกรอง Bloom ที่เสถียร ซึ่งประกอบด้วยตัวกรอง Bloom แบบนับ โดยการแทรกองค์ประกอบใหม่จะตั้งค่าตัวนับที่เกี่ยวข้องเป็นค่าcจากนั้นตัวนับจำนวนคงที่s เท่านั้น ที่จะลดลง 1 ดังนั้นหน่วยความจำส่วนใหญ่จึงมีข้อมูลเกี่ยวกับองค์ประกอบล่าสุด (โดยสัญชาตญาณ เราสามารถสันนิษฐานได้ว่าอายุการใช้งานขององค์ประกอบภายใน SBF ของ ตัวนับ Nนั้นอยู่ที่ประมาณ) อีกวิธีหนึ่งคือตัวกรอง Bloom ที่เสื่อมสภาพ ซึ่งประกอบด้วยตัวกรอง Bloom สองตัว แต่ละตัวใช้พื้นที่ครึ่งหนึ่งของหน่วยความจำทั้งหมดที่มีอยู่ เมื่อตัวกรองหนึ่งเต็ม ตัวกรองที่สองจะถูกลบออก และองค์ประกอบใหม่จะถูกเพิ่มเข้าไปในตัวกรองที่ว่างเปล่าใหม่นี้^{[ 44 ]}${\displaystyle c{\tfrac {s}{N}}}$

อย่างไรก็ตาม ได้มีการแสดงให้เห็นแล้ว^{[ 45 ]}ว่าไม่ว่าตัวกรองจะเป็นอย่างไร หลังจาก แทรก n ครั้ง ผล รวมของความน่าจะเป็นบวกเท็จและลบเท็จจะถูกจำกัดด้านล่างโดยที่Lคือจำนวนขององค์ประกอบที่เป็นไปได้ทั้งหมด (ขนาดของตัวอักษร) m คือ ขนาดของหน่วยความจำ (ในบิต) โดยสมมติว่าผลลัพธ์นี้แสดงให้เห็นว่าสำหรับLที่มากพอและnที่เข้าสู่ค่าอนันต์ ขอบเขตล่างจะลู่เข้าสู่ซึ่งเป็นความสัมพันธ์ลักษณะเฉพาะของตัวกรองแบบสุ่ม ดังนั้น หลังจากแทรกมากพอ และหากตัวอักษรมีขนาดใหญ่เกินกว่าจะจัดเก็บในหน่วยความจำได้ (ซึ่งสมมติไว้ในบริบทของตัวกรองความน่าจะเป็น) เป็นไปไม่ได้ที่ตัวกรองจะทำงานได้ดีกว่าการสุ่ม ผลลัพธ์นี้สามารถใช้ประโยชน์ได้โดยการคาดหวังว่าตัวกรองจะทำงานบนหน้าต่างเลื่อนแทนที่จะเป็นสตรีมทั้งหมด ในกรณีนี้ เลขชี้กำลังnในสูตรข้างต้นจะถูกแทนที่ด้วยwซึ่งให้สูตรที่อาจเบี่ยงเบนจาก 1 หากwไม่เล็กเกินไป ${\displaystyle FP}$${\displaystyle FN}$$${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$$${\displaystyle n>m}$${\displaystyle FP+FN=1}$

Chazelle et al. (2004)ได้ออกแบบตัวกรอง Bloom ที่สามารถกำหนดค่าให้กับแต่ละองค์ประกอบที่ถูกแทรกเข้าไป โดยใช้โครงสร้างอาร์เรย์แบบเชื่อมโยงเช่นเดียวกับตัวกรอง Bloom โครงสร้างเหล่านี้ใช้พื้นที่จัดเก็บข้อมูลน้อยลงโดยยอมรับความน่าจะเป็นของผลลัพธ์ที่ผิดพลาด (false positives) เพียงเล็กน้อย ในกรณีของ "ตัวกรอง Bloomier" ผลลัพธ์ที่ผิดพลาดจะถูกกำหนดให้เป็นการส่งคืนผลลัพธ์เมื่อคีย์ไม่อยู่ในแผนที่ แผนที่จะไม่ส่งคืนค่าที่ไม่ถูกต้องสำหรับคีย์ที่อยู่ในแผนที่

Boldi & Vigna (2005)เสนอการขยายแนวคิดของ Bloom filter โดยใช้ โครงสร้าง แลตทิซ ตัวประมาณค่าแบบกะทัดรัดจะเชื่อมโยงแต่ละคีย์กับองค์ประกอบของแลตทิซ (โดย Bloom filter มาตรฐานใช้แลตทิซแบบบูลีนสององค์ประกอบ) แทนที่จะใช้บิตอาร์เรย์ พวกมันใช้อาร์เรย์ขององค์ประกอบแลตทิซ เมื่อเพิ่มการเชื่อมโยงใหม่ระหว่างคีย์กับองค์ประกอบของแลตทิซ พวกมันจะคำนวณค่าสูงสุดของเนื้อหาปัจจุบันใน ตำแหน่งอาร์เรย์ kตำแหน่งที่เชื่อมโยงกับคีย์นั้นกับองค์ประกอบแลตทิซ เมื่ออ่านค่าที่เชื่อมโยงกับคีย์ พวกมันจะคำนวณค่าต่ำสุดของค่าที่พบใน ตำแหน่ง kตำแหน่งที่เชื่อมโยงกับคีย์นั้น ค่าที่ได้จะประมาณค่าจากค่าด้านบนของค่าเดิม

การใช้งานนี้ใช้อาร์เรย์แยกต่างหากสำหรับแต่ละฟังก์ชันแฮช วิธีนี้ช่วยให้สามารถคำนวณแฮชแบบขนานได้ทั้งสำหรับการแทรกและการสอบถาม^{[ 46 ]}

Almeida et al. (2007)เสนอ Bloom filter รูปแบบหนึ่งที่สามารถปรับเปลี่ยนได้แบบไดนามิกตามจำนวนองค์ประกอบที่จัดเก็บ ในขณะเดียวกันก็รับประกันความน่าจะเป็นของผลบวกเท็จที่น้อยที่สุด เทคนิคนี้ใช้ลำดับของ Bloom filter มาตรฐานที่มีความจุเพิ่มขึ้นและความน่าจะเป็นของผลบวกเท็จที่เข้มงวดมากขึ้น เพื่อให้มั่นใจได้ว่าสามารถกำหนดความน่าจะเป็นของผลบวกเท็จสูงสุดไว้ล่วงหน้าได้ โดยไม่คำนึงถึงจำนวนองค์ประกอบที่จะแทรก

ตัวกรอง Spatial Bloom (SBF) ได้รับการเสนอครั้งแรกโดยPalmieri, Calderoni & Maio (2014)ในฐานะโครงสร้างข้อมูลที่ออกแบบมาเพื่อจัดเก็บข้อมูลตำแหน่งโดยเฉพาะอย่างยิ่งในบริบทของโปรโตคอลการเข้ารหัสลับสำหรับความเป็นส่วนตัว ของตำแหน่ง อย่างไรก็ตาม คุณลักษณะหลักของ SBF คือความสามารถในการจัดเก็บชุดข้อมูลหลายชุดในโครงสร้างข้อมูลเดียว ซึ่งทำให้เหมาะสำหรับสถานการณ์การใช้งานที่แตกต่างกันหลายประการ^{[ 47 ]}สามารถสอบถามการเป็นสมาชิกขององค์ประกอบในชุดข้อมูลเฉพาะได้ และความน่าจะเป็นของผลบวกเท็จขึ้นอยู่กับชุดข้อมูล: ชุดข้อมูลแรกๆ ที่ป้อนเข้าไปในตัวกรองระหว่างการสร้างจะมีความน่าจะเป็นของผลบวกเท็จสูงกว่าชุดข้อมูลที่ป้อนในตอนท้าย^{[ 48 ]}คุณสมบัตินี้ช่วยให้สามารถจัดลำดับความสำคัญของชุดข้อมูลได้ โดยชุดข้อมูลที่มีองค์ประกอบที่ "สำคัญ" มากกว่าจะถูกเก็บรักษาไว้

ตัวกรอง Bloom แบบหลายชั้นประกอบด้วยชั้นตัวกรอง Bloom หลายชั้น ตัวกรอง Bloom แบบหลายชั้นช่วยให้สามารถติดตามจำนวนครั้งที่รายการถูกเพิ่มลงในตัวกรอง Bloom โดยการตรวจสอบว่ามีกี่ชั้นที่มีรายการนั้นอยู่ ด้วยตัวกรอง Bloom แบบหลายชั้น การดำเนินการตรวจสอบโดยปกติจะส่งคืนหมายเลขชั้นที่ลึกที่สุดที่พบรายการนั้น^{[ 49 ]}

ตัวกรอง Bloom ที่ลดทอนลงที่มีความลึก D สามารถมองได้ว่าเป็นอาร์เรย์ของตัวกรอง Bloom ปกติ D ตัว ในบริบทของการค้นหาบริการในเครือข่าย แต่ละโหนดจะจัดเก็บตัวกรอง Bloom ปกติและที่ลดทอนลงไว้ในพื้นที่ ตัวกรอง Bloom ปกติหรือในพื้นที่จะระบุว่าโหนดนั้นให้บริการอะไรบ้าง ตัวกรองที่ลดทอนลงระดับ i จะระบุว่าสามารถพบบริการใดได้บ้างในโหนดที่อยู่ห่างจากโหนดปัจจุบันเป็นระยะ i-hop ค่าที่ i จะถูกสร้างขึ้นโดยการนำค่าตัวกรอง Bloom ในพื้นที่ของโหนดที่อยู่ห่างจากโหนดเป็นระยะ i-hop มารวมกัน^{[ 50 ]}

ตัวอย่างเช่น พิจารณาเครือข่ายขนาดเล็กดังแสดงในกราฟด้านล่าง สมมติว่าเรากำลังค้นหาบริการ A ซึ่งรหัสประจำตัวถูกแฮชเป็นบิต 0, 1 และ 3 (รูปแบบ 11010) ให้โหนด n1 เป็นจุดเริ่มต้น ก่อนอื่น เราตรวจสอบว่าโหนด n1 ให้บริการ A หรือไม่โดยการตรวจสอบตัวกรองภายใน เนื่องจากรูปแบบไม่ตรงกัน เราจึงตรวจสอบตัวกรอง Bloom ที่ลดทอนลงเพื่อพิจารณาว่าโหนดใดควรเป็นฮอปถัดไป เราพบว่าโหนด n2 ไม่ได้ให้บริการ A แต่ตั้งอยู่บนเส้นทางไปยังโหนดที่ให้บริการ ดังนั้นเราจึงย้ายไปยังโหนด n2 และทำซ้ำขั้นตอนเดียวกัน เราพบอย่างรวดเร็วว่าโหนด n3 ให้บริการ และด้วยเหตุนี้จึงพบปลายทาง^{[ 51 ]}

โดยการใช้ตัวกรอง Bloom ที่ลดทอนซึ่งประกอบด้วยหลายชั้น บริการที่ระยะห่างมากกว่าหนึ่งฮอปสามารถค้นพบได้ในขณะที่หลีกเลี่ยงการอิ่มตัวของตัวกรอง Bloom โดยการลดทอน (เลื่อนออก) บิตที่ตั้งค่าโดยแหล่งที่มาที่อยู่ไกลออกไป^{[ 50 ]}

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

ลายนิ้วมือโมเลกุลเริ่มต้นขึ้นในช่วงปลายทศวรรษ 1940 ในฐานะวิธีการค้นหาโครงสร้างทางเคมีบนบัตรเจาะรู อย่างไรก็ตาม จนกระทั่งประมาณปี 1990 บริษัท Daylight Chemical Information Systems, Inc. ได้นำเสนอวิธีการแบบแฮชเพื่อสร้างบิตแทนการใช้ตารางที่คำนวณไว้ล่วงหน้า ซึ่งแตกต่างจากวิธีการใช้พจนานุกรม วิธีการแบบแฮชสามารถกำหนดบิตให้กับโครงสร้างย่อยที่ไม่เคยพบเห็นมาก่อนได้ ในช่วงต้นทศวรรษ 1990 คำว่า "ลายนิ้วมือ" ถูกมองว่าแตกต่างจาก "คีย์โครงสร้าง" แต่ต่อมาคำนี้ได้ขยายขอบเขตไปครอบคลุมลักษณะเฉพาะของโมเลกุลส่วนใหญ่ที่สามารถใช้สำหรับการเปรียบเทียบความคล้ายคลึงกัน รวมถึงคีย์โครงสร้าง ลายนิ้วมือแบบนับจำนวนแบบเบาบาง และลายนิ้วมือ 3 มิติ แตกต่างจาก Bloom filter วิธีการแฮชของ Daylight อนุญาตให้จำนวนบิตที่กำหนดต่อคุณลักษณะเป็นฟังก์ชันของขนาดคุณลักษณะ แต่การใช้งานลายนิ้วมือแบบ Daylight ส่วนใหญ่ใช้จำนวนบิตคงที่ต่อคุณลักษณะ ซึ่งทำให้พวกมันกลายเป็น Bloom filter ลายนิ้วมือ Daylight ดั้งเดิมสามารถใช้ได้ทั้งเพื่อวัตถุประสงค์ในการเปรียบเทียบความคล้ายคลึงและการคัดกรอง ลายนิ้วมือประเภทอื่นๆ อีกมากมาย เช่น ECFP2 ที่ได้รับความนิยม สามารถใช้สำหรับการเปรียบเทียบความคล้ายคลึงได้ แต่ไม่สามารถใช้สำหรับการคัดกรองได้ เพราะลายนิ้วมือเหล่านั้นมีลักษณะเฉพาะของสภาพแวดล้อมเฉพาะที่ ซึ่งอาจทำให้เกิดผลลบเท็จเมื่อใช้เป็นการคัดกรอง แม้ว่าลายนิ้วมือเหล่านี้จะถูกสร้างขึ้นด้วยกลไกเดียวกัน แต่ก็ไม่ใช่ตัวกรอง Bloom เพราะไม่สามารถใช้ในการกรองได้

•  โครงสร้างข้อมูลเชิงความน่าจะเป็นในวิทยาการคอมพิวเตอร์ เรียกว่าCount–min sketch
• การแฮชคุณลักษณะ  – การแปลงคุณลักษณะให้เป็นเวกเตอร์โดยใช้ฟังก์ชันแฮช
• MinHash  – เทคนิคการขุดข้อมูล
• ตัวกรองผลหาร
• รายการข้าม (Skip list)  – โครงสร้างข้อมูลเชิงความน่าจะเป็น
• ตัวกรอง Bloom ในชีวสารสนเทศ
• ตัวกรอง Cuckoo  – โครงสร้างข้อมูลสำหรับการประมาณค่าสมาชิกเซต

Wikimedia Commons มีสื่อที่เกี่ยวข้องกับBloom filter

• "การใช้ Bloom Filter"คำอธิบาย Bloom Filter อย่างละเอียดโดยใช้ภาษา Perl
• เหตุใดตัวกรอง Bloom จึงทำงานได้เช่นนั้น (ไมเคิล นีลเซน, 2012)
• ตัวกรองบลูม — บทช่วยสอน การวิเคราะห์ และการสำรวจ (บลูสไตน์และเอล-มาซาวี, 2002)ที่มหาวิทยาลัยดัลฮาวซี
• ตารางแสดงอัตราผลบวกเท็จสำหรับการกำหนดค่าต่างๆจากเว็บไซต์ของมหาวิทยาลัยวิสคอนซิน–แมดิสัน
• "ตัวกรอง Bloom ที่เหมาะสมยิ่งขึ้น" โดย Ely Porat (พฤศจิกายน 2550) วิดีโอ Google TechTalkบนYouTube