- हम पहले मेमोरी ब्लॉक का चयन करते हैं।
- फिर हम प्रत्येक ब्लॉक के भीतर स्थानीय ब्लूम फ़िल्टर का चयन करते हैं।
- यह मेमोरी ब्लॉक के बीच असंतुलन पैदा कर सकता है
- यह फ़िल्टर कुशल है, लेकिन खराब झूठी सकारात्मक दर (FPR) है।
- पहली बार में, ब्लॉक किए गए ब्लूम फ़िल्टर में समान आकार के मानक ब्लूम फ़िल्टर के समान FPR (गलत सकारात्मक दर) होना चाहिए।
- ब्लॉक किए गए ब्लूम फ़िल्टर में मानक ब्लूम फ़िल्टर (ब्लूम फ़िल्टर ब्लॉक) की तुलना में तुलनात्मक रूप से कम ब्लॉक b का अनुक्रम होता है, जिनमें से प्रत्येक एक कैश-लाइन में फ़िट हो जाता है।
- अवरुद्ध ब्लूम फ़िल्टर योजना को विभाजन योजनाओं से अलग किया जाता है, जहां प्रत्येक बिट को एक अलग ब्लॉक में डाला जाता है।
अवरुद्ध ब्लूम फ़िल्टर निम्नलिखित तरीकों से कार्यान्वित किया जाता है -
बिट पैटर्न (पैट)
इस विषय में, हम पहले से गणना किए गए बिट पैटर्न को लागू करने वाले अवरुद्ध ब्लूम फ़िल्टर को लागू करने के लिए चर्चा करते हैं। k हैश फ़ंक्शन के मूल्यांकन के माध्यम से k बिट्स सेट करने के बजाय, एक एकल हैश फ़ंक्शन चौड़ाई B के यादृच्छिक k-बिट पैटर्न की तालिका से एक पूर्व-गणना पैटर्न का चयन करता है। कई मामलों में, यह तालिका कैश में फिट होगी। इस समाधान के साथ, केवल एक छोटे (बिट्स के संदर्भ में) हैश मान की आवश्यकता होती है, और ऑपरेशन को कुछ SIMD (सिंगल इंस्ट्रक्शन मल्टीपल डेटा) निर्देशों का उपयोग करके लागू किया जा सकता है। ब्लूम फ़िल्टर को स्थानांतरित करते समय, तालिका को डेटा में स्पष्ट रूप से शामिल करने की आवश्यकता नहीं है, लेकिन बीज मूल्य को लागू करके इसे फिर से बनाया जा सकता है।
बिट पैटर्न विधि का मुख्य नुकसान यह है कि दो तत्व एक ही पैटर्न में हैश किए जाने पर टेबल टकराव का कारण बन सकते हैं। इससे एफपीआर बढ़ जाता है।
मल्टीप्लेक्सिंग पैटर्न
इस विचार को एक बार फिर परिशोधित करने के लिए, हम k/x सेट बिट्स की औसत संख्या के साथ बिटवाइज़-या-इंग x पैटर्न द्वारा एकल तालिका से बड़ी विविधता वाले पैटर्न प्राप्त कर सकते हैं।
मल्टी-ब्लॉकिंग
एक और प्रकार जो एफपीआर को बेहतर बनाने में मदद करता है, उसे मल्टी-ब्लॉकिंग कहा जाता है। हम प्रत्येक ब्लॉक में क्रमशः के/एक्स बिट्स की सेटिंग या परीक्षण करने के लिए एक्स ब्लूम फिल्टर ब्लॉक तक पहुंचने के लिए क्वेरी ऑपरेशन की अनुमति देते हैं। (जब k, X से विभाज्य नहीं होता है, तो हम पहले k mod X ब्लॉक में एक अतिरिक्त बिट सेट करते हैं।) मल्टी-ब्लॉकिंग केवल ब्लॉक आकार को XB (B-प्रत्येक ब्लॉक आकार) तक बढ़ाने से बेहतर प्रदर्शन करता है, क्योंकि इसमें अधिक विविधता पेश की जाती है। मार्ग। यदि हम सेट बिट्स को कई ब्लॉकों में विभाजित करते हैं, तो प्रति ब्लॉक 1 बिट की अपेक्षित संख्या समान रहती है। हालांकि, किसी तत्व को एक्सेस करते समय, प्रत्येक प्रतिभागी ब्लॉक में केवल k/X बिट्स पर विचार किया जाता है।