- हम पहले एक मेमोरी ब्लॉक (Memory Block) चुनते हैं।
- फिर हम प्रत्येक ब्लॉक के भीतर लोकल ब्लूम फिल्टर (Local Bloom Filter) चुनते हैं।
- इससे मेमोरी ब्लॉक्स के बीच असंतुलन (Imbalance) हो सकता है।
- यह फिल्टर कुशल (Efficient) है, लेकिन खराब फाल्स पॉजिटिव रेट (False Positive Rate - FPR) है।
- पहले उदाहरण में, ब्लॉक्ड ब्लूम फिल्टर्स का FPR समान आकार के स्टैंडर्ड ब्लूम फिल्टर्स के समान होना चाहिए।
- ब्लॉक्ड ब्लूम फिल्टर में ब्लॉक b का एक क्रम होता है जो स्टैंडर्ड ब्लूम फिल्टर्स (ब्लूम फिल्टर ब्लॉक्स) की तुलना में तुलनात्मक रूप से कम होता है, जिनमें से प्रत्येक एक कैश-लाइन (Cache-line) में फिट बैठता है।
- ब्लॉक्ड ब्लूम फिल्टर स्कीम पार्टीशन स्कीम्स (Partition Schemes) से अलग है, जहां प्रत्येक बिट को अलग ब्लॉक में डाला जाता है।
ब्लॉक्ड ब्लूम फिल्टर को निम्न तरीकों से लागू किया जाता है −
बिट पैटर्न्स (Bit Patterns - pat)
इस विषय में, हम प्रीकंप्यूटेड बिट पैटर्न (Precomputed Bit Patterns) लागू करके ब्लॉक्ड ब्लूम फिल्टर्स को लागू करने पर चर्चा करते हैं। k हैश फंक्शन्स के मूल्यांकन के माध्यम से k बिट्स सेट करने के बजाय, एक सिंगल हैश फंक्शन चौड़ाई B के रैंडम k-बिट पैटर्न की एक टेबल से प्रीकंप्यूटेड पैटर्न का चयन करता है। कई मामलों में, यह टेबल कैश में फिट हो जाएगी। इस समाधान के साथ, केवल एक छोटा (बिट्स के संदर्भ में) हैश मान आवश्यक है, और ऑपरेशन को कुछ SIMD (सिंगल इंस्ट्रक्शन मल्टीपल डेटा) निर्देशों का उपयोग करके लागू किया जा सकता है। ब्लूम फिल्टर ट्रांसफर करते समय, टेबल को डेटा में स्पष्ट रूप से शामिल करने की आवश्यकता नहीं है, लेकिन सीड वैल्यू (Seed Value) का उपयोग करके पुनर्निर्मित किया जा सकता है।
बिट पैटर्न मेथड का मुख्य नुकसान यह है कि दो एलिमेंट्स टेबल टकराव (Table Collision) का कारण बन सकते हैं जब वे उसी पैटर्न पर हैश होते हैं। इससे FPR बढ़ जाता है।
मल्टीप्लेक्सिंग पैटर्न्स (Multiplexing Patterns)
इस विचार को एक बार और परिष्कृत करने के लिए, हम एक सिंगल टेबल से बिटवाइज़-OR (Bitwise-OR) करके x पैटर्न को औसतन k/x सेट बिट्स के साथ जोड़कर पैटर्न की एक बड़ी विविधता प्राप्त कर सकते हैं।
मल्टी-ब्लॉकिंग (Multi-Blocking)
एक और संस्करण जो FPR सुधारने में मदद करता है, उसे मल्टी-ब्लॉकिंग कहा जाता है। हम क्वेरी ऑपरेशन को X ब्लूम फिल्टर ब्लॉक्स तक पहुंचने की अनुमति देते हैं, प्रत्येक ब्लॉक में क्रमशः k/X बिट्स सेट या टेस्ट करते हैं। (जब k X से विभाज्य नहीं होता, तो हम पहले k mod X ब्लॉक्स में एक अतिरिक्त बिट सेट करते हैं।) मल्टी-ब्लॉकिंग केवल ब्लॉक आकार को XB (B-प्रत्येक ब्लॉक आकार) बढ़ाने से बेहतर प्रदर्शन करता है, क्योंकि इस तरह अधिक विविधता पेश की जाती है। यदि हम कई ब्लॉक्स में सेट बिट्स को विभाजित करते हैं, तो प्रति भाग लेने वाले ब्लॉक में अपेक्षित 1 बिट की संख्या समान रहती है। हालांकि, एक एलिमेंट तक पहुँचते समय प्रत्येक भाग लेने वाले ब्लॉक में केवल k/X बिट्स पर विचार किया जाता है।
