ब्लूम निस्यंदक

Not to be confused with ब्लूम शेडर इफेक्ट.

ब्लूम निस्यंदक एक समष्टि-कुशल संभाव्य प्रदत्त संरचना है, जिसे 1970 में बर्टन हावर्ड ब्लूम द्वारा परिकल्पित किया गया था, जिसका उपयोग यह परीक्षण करने के लिए किया जाता है कि क्या कोई तत्व एक समुच्चय का घटक है। मिथ्या सकारात्मकता मिलान संभव हैं, परन्तु मिथ्या अपवर्जित नहीं हैं - दूसरे शब्दों में, एक परिप्रश्न या तो "संभवतः समुच्चय में" या "निश्चित रूप से समुच्चय में नहीं" होती है। तत्वों को समुच्चय में जोड़ा जा सकता है, परन्तु पदच्युत नहीं किया जा सकता (हालांकि इसे गणना ब्लूम निस्यंदक संस्करण के साथ संबोधित किया जा सकता है); जितने अधिक पद जोड़े जाते हैं, मिथ्या सकारात्मकता की संभाव्यता उतनी ही अधिक होती है।

ब्लूम ने उन अनुप्रयोगों के लिए प्रविधि प्रस्तावित की जहां "पारंपरिक" त्रुटि मुक्त द्रुतान्वेषण प्रविधियों को अनुप्रयुक्त करने पर स्रोत प्रदत्त की मात्रा में अव्यावहारिक रूप से बड़ी मात्रा में मेमोरी की आवश्यकता होगी। उन्होंने 500,000 शब्दों के शब्दकोश के लिए एक शब्द संयोजकता कलन विधि का उदाहरण दिया, जिसमें से 90% सरल शब्द संयोजकता नियमों का पालन करते हैं, परन्तु शेष 10% को विशिष्ट शब्द संयोजकता प्रतिरूप को पुनः प्राप्त करने के लिए बहुमूल्य चक्रिका अभिगमन की आवश्यकता होती है। पर्याप्त कोर मेमोरी के साथ, सभी अनावश्यक चक्रिका अभिगमन को समाप्त करने के लिए एक त्रुटि-मुक्त द्रुतान्वेषण का उपयोग किया जा सकता है; दूसरी ओर, सीमित कोर मेमोरी के साथ, ब्लूम की प्रविधि एक छोटे द्रुतान्वेषण क्षेत्र का उपयोग करती है परन्तु फिर भी अधिकांश अनावश्यक अभिगमन को समाप्त कर देती है। उदाहरण के लिए, एक आदर्श त्रुटि-मुक्त द्रुतान्वेषण के लिए आवश्यक आकार का केवल 15% द्रुतान्वेषण क्षेत्र अभी भी 85% चक्रिका अभिगमन को समाप्त करता है।

सामान्यतः, समुच्चय में तत्वों के आकार या संख्या से स्वतंत्र, 1% मिथ्या सकारात्मकता संभाव्यता के लिए प्रति तत्व 10 द्वयंक से कम की आवश्यकता होती है।

कलन विधि विवरण

File:Bloom filter.svg

समुच्चय का प्रतिनिधित्व करने वाले ब्लूम निस्यंदक का एक उदाहरण {x, y, z} . रंगीन तीर द्वयंक सरणी में स्थिति दिखाते हैं कि प्रत्येक समुच्चय तत्व को प्रतिचित्र किया गया है। तत्व w समुच्चय में नहीं है {x, y, z} , क्योंकि यह 0 वाली एक द्वयंक-सरणी स्थिति के लिए द्रुतान्वेषण है। इस प्रदत्त के लिए, m = 18 और k = 3.

एक अपूरित ब्लूम निस्यंदक m द्वयंक की एक द्वयंक सरणी है, सभी 0 पर व्यवस्थित है। इसमें k अलग-अलग द्रुतान्वेषण फलन भी परिभाषित होने चाहिए, जिनमें से प्रत्येक एक समान यादृच्छिक वितरण उत्पन्न करते हुए, m सरणी स्थितियों में से किसी एक के लिए कुछ समुच्चय तत्व को प्रतिचित्र या द्रुतान्वेषण करता है। विशिष्ट रूप से, k एक छोटा स्थिरांक है जो वांछित मिथ्य त्रुटि दर ε पर निर्भर करता है, जबकि m के लिए k आनुपातिक है और जोड़े जाने वाले तत्वों की संख्या के समानुपाती होता है।

एक तत्व जोड़ने के लिए, k सरणी स्थिति प्राप्त करने के लिए इसे प्रत्येक k द्रुतान्वेषण फलन में भरण करें। इन सभी स्थितियों पर द्वयंक को 1 पर व्यवस्थित करें।

किसी तत्व के लिए परिप्रश्न करने के लिए (परीक्षण करें कि यह समुच्चय में है या नहीं), k सरणी स्थिति प्राप्त करने के लिए इसे प्रत्येक k द्रुतान्वेषण फलन में भरण करें। यदि इन स्थितियों में से कोई भी द्वयंक 0 है, तो तत्व निश्चित रूप से समुच्चय में नहीं है; यदि ऐसा होता, तो सभी द्वयंक को सम्मिलित करते समय 1 पर व्यवस्थित किया गया होता। यदि सभी 1 हैं, तो या तो तत्व समुच्चय में है, या द्वयंक को अन्य तत्वों के अंतर्वेशन के पर्यन्त संयोग से 1 पर समुच्चय किया गया है, जिसके परिणामस्वरूप एक मिथ्या सकारात्मक है। एक साधारण ब्लूम निस्यंदक में, दो स्थितियों के मध्य अंतर करने का कोई तरीका नहीं है, परन्तु अधिक उन्नत प्रविधियां इस समस्या का समाधान कर सकती हैं।

बड़े k के लिए k विभिन्न स्वतंत्र द्रुतान्वेषण फलन को अभिकल्पन करने की आवश्यकता निषेधात्मक हो सकती है। एक विस्तृत प्रक्षेपण के साथ एक अच्छे द्रुतान्वेषण फलन के लिए, इस तरह के द्रुतान्वेषण के विभिन्न द्वयंक-क्षेत्र के मध्य कोई संबंध होने पर बहुत कम होना चाहिए, इसलिए इस प्रकार के द्रुतान्वेषण का उपयोग इसके प्रक्षेपण को कई द्वयंक-क्षेत्र में स्तरकर्तन करके कई "विभिन्न" द्रुतान्वेषण फलन उत्पन्न करने के लिए किया जा सकता है। वैकल्पिक रूप से, एक द्रुतान्वेषण फलन के लिए k विभिन्न प्रारंभिक मान (जैसे 0, 1, ..., k − 1) पास कर सकते हैं जो प्रारंभिक मान लेता है; या इन मानों को कुंजी में जोड़ें (या जोड़ें)। बड़े m और/या k के लिए, मिथ्या सकारात्मक दर में नगण्य वृद्धि के साथ द्रुतान्वेषण फलनों के मध्य स्वतंत्रता को शिथिल कर दिया जा सकता है। (विशेष रूप से, डिलिंगर और मैनोलिओस (2004बी) उन्नत द्विक द्रुतान्वेषण और त्रिक द्रुतान्वेषण का उपयोग करके, k सूचकांकों को प्राप्त करने की प्रभावशीलता दर्शाते हैं, द्विक द्रुतान्वेषण के भिन्नरूप जो प्रभावी रूप से दो या तीन द्रुतान्वेषण मानों के साथ प्रभावी रूप से सरल यादृच्छिक संख्या जनक हैं)।

इस सरल ब्लूम निस्यंदक से किसी तत्व को हटाना असंभव है क्योंकि यह बताने का कोई तरीका नहीं है कि यह किस k द्वयंक को प्रतिचित्र करता है उन्हें साफ़ किया जाना चाहिए। हालांकि उन k द्वयंक में से किसी एक को शून्य पर व्यवस्थित करना तत्व को पदच्युत करने के लिए पर्याप्त है, यह उस द्वयंक पर प्रतिचित्र करने के लिए होने वाले किसी अन्य तत्व को भी पदच्युत कर देगा। चूंकि सरल कलन विधि यह निर्धारित करने का कोई तरीका नहीं प्रदान करता है कि क्या कोई अन्य तत्व जोड़ा गया है जो तत्व को हटाने के लिए द्वयंक को प्रभावित करता है, किसी भी द्वयंक को साफ़ करने से मिथ्या नकारात्मकता की संभाव्यता उत्पन्न होगी।

ब्लूम निस्यंदक से किसी तत्व को एक बार हटाने के लिए एक दूसरे ब्लूम निस्यंदक का अनुकरण किया जा सकता है, जिसमें हटाए गए पद सम्मिलित हैं। हालांकि, दूसरे निस्यंदक में मिथ्या सकारात्मक समग्र निस्यंदक में मिथ्या नकारात्मक बन जाती है, जो अवांछित हो सकती है। इस दृष्टिकोण में पूर्व से हटाए गए पद को पुनः जोड़ना संभव नहीं है, क्योंकि किसी को इसे हटाए गए निस्यंदक से हटाना होगा।

प्रायः ऐसा होता है कि सभी कुंजियाँ उपलब्ध होती हैं, परन्तु गणना करना बहुमूल्य होता है (उदाहरण के लिए, कई चक्रिका पढ़ने की आवश्यकता होती है)। जब मिथ्या सकारात्मक दर बहुत अधिक हो जाती है, तो निस्यंदक को पुन: उत्पन्न किया जा सकता है; यह एक अपेक्षाकृत दुर्लभ घटना होनी चाहिए।

दिक्समष्टि और समय के लाभ

File:Bloom filter speed.svg

ब्लूम निस्यंदक का उपयोग की-वैल्यू संग्रहीतेज सिस्टम में उत्तरों को गति देने के लिए किया जाता है। मान उस चक्रिका पर संग्रहीत होते हैं जिसका अभिगमन समय धीमा होता है। ब्लूम निस्यंदक निर्णय बहुत तीव्र होते हैं। हालाँकि, कुछ अनावश्यक चक्रिका अभिगमन तब किए जाते हैं जब निस्यंदक एक सकारात्मक रिपोर्ट करता है (गलत सकारात्मक को हटाने के लिए)। ब्लूम निस्यंदक के बिना समग्र उत्तर गति ब्लूम निस्यंदक के साथ उन्नत है। हालाँकि, इस उद्देश्य के लिए ब्लूम निस्यंदक का उपयोग करने से स्मृति उपयोग में वृद्धि होती है.

मिथ्या सकारात्मकताओं को संकट में डालते हुए, ब्लूम निस्यंदक के पास समुच्चय का प्रतिनिधित्व करने के लिए अन्य प्रदत्त संरचनाओं पर पर्याप्त समष्टि लाभ होता है, जैसे स्व-संतुलन द्विचर अन्वेषण ट्री, प्रयास, द्रुतान्वेषण तालिका , या सरल सरणी प्रदत्त संरचना या प्रविष्टियों की संलग्न सूची है। इनमें से अधिकांश को कम से कम प्रदत्त पद को संग्रहीत करने की आवश्यकता होती है, जिसके लिए द्वयंक की एक छोटी संख्या से कहीं भी आवश्यकता हो सकती है, छोटे पूर्णांक के लिए, द्वयंक की यादृच्छिक संख्या के लिए, जैसे श्रृंखला के लिए (प्रयास एक अपवाद हैं क्योंकि वे तत्वों के मध्य भंडारण समान उपसर्गों के साथ साझा कर सकते हैं)। हालाँकि, ब्लूम निस्यंदक प्रदत्त पद को पूर्णतया संग्रहीत नहीं करता है, और वास्तविक संग्रहण के लिए एक अलग समाधान प्रदान किया जाना चाहिए। संलग्न संरचनाओं में संकेतक के लिए एक अतिरिक्त रैखिक समष्टि उपरि होता है। 1% त्रुटि वाला एक ब्लूम निस्यंदक और इसके विपरीत k का इष्टतम मान, तत्वों के आकार की उपेक्षा किए बिना प्रति तत्व केवल लगभग 9.6 द्वयंक की आवश्यकता होती है। यह लाभ आंशिक रूप से इसकी संहतता से आता है, जो सरणियों और आंशिक रूप से इसकी संभाव्य प्रकृति से विरासत में मिला है। प्रति तत्व केवल 4.8 द्वयंक जोड़कर 1% मिथ्या-सकारात्मक दर को दस के कारक से कम किया जा सकता है।

हालाँकि, यदि संभावित मानों की संख्या कम है और उनमें से कई समुच्चय में हो सकते हैं, तो ब्लूम निस्यंदक को नियतात्मक द्वयंक सरणी द्वारा सरलता से पार कर लिया जाता है, जिसके लिए प्रत्येक संभावित तत्व के लिए केवल एक द्वयंक की आवश्यकता होती है। द्रुतान्वेषण तालिकाएँ समष्टि और समय का लाभ प्राप्त करती हैं यदि वे संघट्टन को अनदेखा करना प्रारंभ करती हैं और केवल तभी संग्रहीत करती हैं जब प्रत्येक समूह में एक प्रविष्टि हो; इस स्थिति में, वे k = 1 के साथ प्रभावी रूप से ब्लूम निस्यंदक बन गए हैं

ब्लूम निस्यंदक में असामान्य गुणधर्म भी होता है कि पद जोड़ने या यह जांचने के लिए समय की आवश्यकता होती है कि कोई पद समुच्चय में है या नहीं, यह एक निश्चित स्थिरांक O(k) है, समुच्चय में पूर्व से उपस्थित पद की संख्या से पूर्णतया स्वतंत्र है। किसी अन्य स्थिर-समष्टि समुच्चय प्रदत्त संरचना में यह गुण नहीं है, परन्तु विरल द्रुतान्वेषण तालिकाओं का औसत अभिगमन समय उन्हें कुछ ब्लूम निस्यंदक की तुलना में तीव्र बना सकता है। हार्डवेयर कार्यान्वयन में, हालांकि, ब्लूम निस्यंदक प्रकाशित होता है क्योंकि इसकी k लुकअप स्वतंत्र हैं और इन्हें समानांतर किया जा सकता है।

इसकी समष्टि दक्षता को समझने के लिए, सामान्य ब्लूम निस्यंदक की तुलना उसके विशेष स्थिति से करना शिक्षाप्रद है जब k = 1 है। यदि k = 1, तब मिथ्या सकारात्मक दर को पर्याप्त रूप से कम रखने के लिए, द्वयंक का एक छोटा सा भिन्न व्यवस्थित किया जाना चाहिए, जिसका अर्थ है कि सरणी बहुत बड़ी होनी चाहिए और इसमें शून्य के लंबे प्रवृति होनी चाहिए। इसके आकार के सापेक्ष सरणी की सूचना सामग्री कम है। सामान्यीकृत ब्लूम निस्यंदक (1 से अधिक k) निम्न मिथ्या सकारात्मक दर को बनाए रखते हुए कई और द्वयंक को समुच्चय करने की अनुमति प्रदान करता है; यदि मापदंडों (k और m) अच्छी तरह से चयन किया जाता हैं, लगभग आधे द्वयंक व्यवस्थित किए जाएंगे, और ये स्पष्ट रूप से यादृच्छिक होंगे, अतिरेक को कम करने और सूचना सामग्री को अधिकतम करने के लिए है।

मिथ्या सकारात्मकता की संभाव्यता

File:Bloom filter fp probability.svg

मिथ्या सकारात्मक संभाव्यता $p$ तत्वों की संख्या के एक समारोह के रूप में $n$ निस्यंदक और निस्यंदक आकार में $m$. द्रुतान्वेषण फलन की इष्टतम संख्या $k=(m/n)\ln 2$ माना गया है।

मान लें कि एक द्रुतान्वेषण फलन प्रत्येक सरणी स्थिति को समान संभाव्यता के साथ चयनित करता है। यदि m सरणी में द्वयंक की संख्या है, संभाव्यता है कि तत्व के अंतर्वेशन के पर्यन्त एक निश्चित द्रुतान्वेषण फलन द्वारा एक निश्चित द्वयंक 1 पर व्यवस्थित नहीं किया जाता है।

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

यदि k द्रुतान्वेषण फलन की संख्या है और प्रत्येक का एक दूसरे के मध्य कोई महत्वपूर्ण संबंध नहीं है, तो संभाव्यता है कि द्वयंक किसी भी द्रुतान्वेषण फलन द्वारा 1 पर व्यवस्थित नहीं है।

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

हम e⁻¹ के लिए प्रसिद्ध पहचान का उपयोग कर सकते हैं।

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

यह बड़े m के लिए निष्कर्ष निकालने के लिए हैं।

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

यदि हमने n तत्व अन्तर्निविष्ट हैं, संभाव्यता है कि एक निश्चित द्वयंक अभी भी 0 है।

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

इसलिए संभाव्यता है कि यह 1 है;

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

अब उस तत्व की सदस्यता का परीक्षण करें, जो समुच्चय में नहीं है। द्रुतान्वेषण फलन द्वारा गणना की गई, प्रत्येक k सरणी स्थिति ऊपर की संभाव्यता के साथ 1 है। उन सभी के 1 होने की प्रायिकता, जो कलन विधि को अनुचित तरीके से अनुरोध करने का कारण बनेगी कि तत्व समुच्चय में है, प्रायः इस रूप में दिया जाता है।

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

यह कठोरता से सही नहीं है क्योंकि यह प्रत्येक द्वयंक की व्यवस्थित करने की संभाव्यताओं के लिए स्वतंत्रता मानता है। हालाँकि, यह मानते हुए कि यह एक निकट सन्निकटन है, हमारे पास यह है कि मिथ्या सकारात्मकता की संभाव्यता घट जाती है क्योंकि m (सरणी में द्वयंक की संख्या) बढ़ जाती है, जैसे n (सम्मिलित तत्वों की संख्या) बढ़ जाती है।

स्वतंत्रता ग्रहण किए बिना, मिथ्या सकारात्मकता की वास्तविक संभाव्यता है।

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

जहां {धनुकोष्ठक} दूसरी तरह की स्टर्लिंग संख्या को दर्शाता है।

स्वाधीनता की धारणा के बिना एक ही सन्निकटन पर पहुंचने वाला एक वैकल्पिक विश्लेषण मिट्ज़ेनमाकर और उपफाल द्वारा दिया गया है। ब्लूम निस्यंदक में सभी n पद जोड़े जाने के पश्चात, माना q को उन m द्वयंक का भिन्न है जो 0 पर व्यवस्थित हैं (अर्थात, अभी भी 0 पर व्यवस्थित किए गए द्वयंक की संख्या qm है)। तत्व समुच्चय में नहीं है, किसी भी k द्रुतान्वेषण फलन द्वारा दी गई सरणी स्थिति के लिए, संभाव्यता है कि द्वयंक 1 पर समुच्चय $1-q$ पाया जाता है। तो संभाव्यता है कि सभी k द्रुतान्वेषण फलन उनके द्वयंक 1 को $(1-q)^{k}$ पर व्यवस्थित करते हैं। इसके अतिरिक्त, q का अपेक्षित मान संभाव्यता है कि दी गई सरणी स्थिति प्रत्येक n पद के लिए प्रत्येक k द्रुतान्वेषण फलन से छूटी हुई है, जो (ऊपर के रूप में) है।

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

यह सिद्ध करना संभव है कि स्वतंत्रता की धारणा के बिना, q अपने अपेक्षित मान के आसपास बहुत दृढ़ता से केंद्रित है। विशेष रूप से, अज़ुमा-होफ़डिंग असमानता से, वे सिद्ध करते हैं कि

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

इसके कारण से, हम कह सकते हैं कि मिथ्या सकारात्मकता की सटीक संभाव्यता है।

$\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 मान जो मिथ्या सकारात्मक संभाव्यता को कम करता है।

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

द्वयंक m की आवश्यक संख्या, दिए गए n (सम्मिलित तत्वों की संख्या) और एक वांछित मिथ्या सकारात्मक संभाव्यता ε (और k के इष्टतम मान का उपयोग किया जाता है) की गणना ऊपर की संभाव्यता अभिव्यक्ति में k के इष्टतम मान को प्रतिस्थापित करके की जा सकती है:

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

जिसे सरल बनाया जा सकता है:

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

इस में यह परिणाम है:

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

तो प्रति तत्व द्वयंक की इष्टतम संख्या है:

${\frac {m}{n}}=-{\frac {\log _{2}\varepsilon }{\ln 2}}\approx -1.44\log _{2}\varepsilon$

द्रुतान्वेषण फलन k की संगत संख्या के साथ (अखंडता की अवहेलना करते हुए):

$k=-{\frac {\ln \varepsilon }{\ln 2}}=-\log _{2}\varepsilon .$

इसका अर्थ यह है कि दी गई मिथ्या सकारात्मक संभाव्यता ε के लिए, ब्लूम निस्यंदक m की लंबाई निस्यंदित किए जाने वाले तत्वों की संख्या के अनुपात में है और द्रुतान्वेषण फलन की आवश्यक संख्या केवल लक्ष्य मिथ्या सकारात्मक संभाव्यता ε पर निर्भर करती है।

सूत्र $m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}$ तीन कारणों से अनुमानित है। सर्वप्रथम और कम से कम चिंता की बात है, यह $1-{\frac {1}{m}}$ जैसे $e^{-{\frac {1}{m}}}$अनुमानित है, जो एक उचित स्पर्शोन्मुख सन्निकटन है (अर्थात, जो m →∞ के रूप में धारण करता है)। दूसरा, अधिक चिंता का विषय, यह मानता है कि सदस्यता परीक्षण के पर्यन्त एक परीक्षण द्वयंक 1 पर व्यवस्थित होने की घटना इस घटना से स्वतंत्र है कि कोई अन्य परीक्षण द्वयंक 1 पर व्यवस्थित है। तीसरा, सबसे अधिक चिंता का विषय, यह मानता है कि $k={\frac {m}{n}}\ln 2$ संयोगवश अभिन्न है।

गोयल और गुप्ता, हालाँकि, एक कठोर ऊपरी सीमा देते हैं जो कोई अनुमान नहीं लगाता है और किसी धारणा की आवश्यकता नहीं है। वे दर्शाते हैं कि m द्वयंक के साथ एक सीमित ब्लूम निस्यंदक के लिए मिथ्या सकारात्मक संभाव्यता ($m>1$) है, n तत्व और k द्रुतान्वेषण फलन अधिकतम है।

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

इस परिबंध की व्याख्या यह कहकर की जा सकती है कि अनुमानित सूत्र $\left(1-e^{-{\frac {kn}{m}}}\right)^{k}$ अधिकतम आधे अतिरिक्त तत्व और अधिकतम एक कम द्वयंक के दंड पर अनुप्रयुक्त किया जा सकता है।

ब्लूम निस्यंदक में पदों की संख्या का अनुमान लगाना

Swamidass & Baldi (2007) ने दर्शाया कि ब्लूम निस्यंदक में पदों की संख्या को निम्न सूत्र से अनुमानित किया जा सकता है,

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

जहाँ $n^{*}$ निस्यंदक में पदों की संख्या का अनुमान, m निस्यंदक की लंबाई (आकार) है, k द्रुतान्वेषण फलन की संख्या है और X पर समुच्चय द्वयंक की संख्या है।

समुच्चय का संघ और प्रतिच्छेदन

ब्लूम निस्यंदक पदों के एक समूह को संक्षिप्त रूप से प्रस्तुत करने का एक तरीका है। दो समुच्चयों के मध्य प्रतिच्छेदन या संघ के आकार की गणना करने का प्रयास करना सामान्य बात है। ब्लूम निस्यंदक का उपयोग प्रतिच्छेदन के आकार और दो समुच्चयों के मिलन का अनुमान लगाने के लिए किया जा सकता है। स्वामीदास और बाल्दी ने दर्शाया कि m लंबाई के दो ब्लूम निस्यंदक के लिए, उनकी गणना का क्रमशः अनुमान लगाया जा सकता है।

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

और

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

उनके संघ के आकार का अनुमान लगाया जा सकता है।

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

जहाँ $n(A\cup B)$ दो ब्लूम निस्यंदकों में से किसी एक में समुच्चय द्वयंक की संख्या है। अंत में, प्रतिच्छेदन का अनुमान लगाया जा सकता है।

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

तीन सूत्रों का एक साथ उपयोग करना है।

रोचक गुणधर्म

• संघट्ट समाधान के लिए विवृत पताभिगमन का उपयोग करने वाली एक मानक द्रुतान्वेषण तालिका के विपरीत, एक निश्चित आकार का ब्लूम निस्यंदक अव्यवस्थिततः बड़ी संख्या में तत्वों के साथ एक समुच्चय का प्रतिनिधित्व कर सकता है; आँकड़ा संरचना भरण के कारण कोई तत्व जोड़ना कभी विफल नहीं होता है। हालाँकि, जब तक निस्यंदक में सभी द्वयंक 1 पर व्यवस्थित नहीं हो जाते, तब तक तत्वों को जोड़े जाने पर मिथ्या सकारात्मक दर निरंतर बढ़ती जाती है, जिस बिंदु पर सभी प्रश्न सकारात्मक परिणाम देते हैं। विवृत पताभिगमन द्रुतान्वेषण के साथ, मिथ्या सकारात्मकता कभी उत्पन्न नहीं होती है, परन्तु जब तक यह रैखिक खोज तक नहीं पहुंचती तब तक प्रदर्शन निरंतर बिगड़ता जाता है।
• समान आकार और द्रुतान्वेषण फलन के समुच्चय वाले ब्लूम निस्यंदक के संघ और प्रतिच्छेदन को क्रमशः बिटवाइज़ संचालन ओआर और एएनडी संचालन के साथ अनुप्रयुक्त किया जा सकता है। ब्लूम निस्यंदक पर संघ संचालन इस अर्थ में दोषरहित है कि परिणामी ब्लूम निस्यंदक दो समुच्चयों के मिलन का उपयोग करके आखुर से बनाए गए ब्लूम निस्यंदक के समान है। प्रतिच्छेद संचालन एक दुर्बल गुणधर्म को संतुष्ट करता है: परिणामी ब्लूम निस्यंदक में मिथ्या सकारात्मक संभाव्यता अधिक-से-अधिक एक घटक ब्लूम निस्यंदक में मिथ्या सकारात्मक संभाव्यता है, परन्तु आखुर से बनाए गए ब्लूम निस्यंदक में दो समुच्चयों का प्रतिच्छेदन मिथ्या सकारात्मक संभाव्यता से बड़ा हो सकता है।
• कुछ प्रकार के अध्यारोपित बीजांक को भौतिक दांतेदार पत्रक के साथ अनुप्रयुक्त किए गए ब्लूम निस्यंदक के रूप में देखा जा सकता है। एक उदाहरण ज़ेटो कूटलेखन है, जिसे 1947 में केल्विन मूर्स द्वारा आविष्कृत किया गया था, जिसमें सूचना के एक खंड से जुड़ी श्रेणियों का समुच्चय एक पत्रक पर चिह्न द्वारा दर्शाया गया है, जिसमें प्रत्येक श्रेणी के लिए चार चिन्हों का एक यादृच्छिक प्रतिरूप है।

उदाहरण

• फल मक्खियाँ गंध की नवीनता का पता लगाने के लिए ब्लूम निस्यंदक के एक संशोधित संस्करण का उपयोग करती है, जिसमें अतिरिक्त विशेषताएं सम्मिलित हैं, जिसमें पूर्व से अनुभव किए गए उदाहरणों की नई गंध की समानता और उसी गंध के पूर्व अनुभव के बाद का समय सम्मिलित है।
• एक सामग्री वितरण प्रदाता अकामाई प्रौद्योगिकियों के परिवेषक, वन-हिट-वंडर्स को अपने चक्रिका द्रुतिका में संग्रहीत होने से रोकने के लिए ब्लूम निस्यंदक का उपयोग करते हैं। वन-हिट-वंडर्स वे संचार वस्तुएँ हैं जिनका उपयोगकर्ताओं द्वारा केवल एक बार अनुरोध किया जाता है, कुछ ऐसा जिसे अकामाई ने पाया कि यह उनके द्रुतीकरण आधारभूत संरचना का लगभग तीन-चौथाई पर अनुप्रयुक्त होता है। संचार वस्तुओं के लिए दूसरे अनुरोध का पता लगाने के लिए ब्लूम निस्यंदक का उपयोग करना और उस वस्तुओं को केवल उसके दूसरे अनुरोध पर द्रुतिका करना, चक्रिका द्रुतिका में प्रवेश करने से वन-हिट-वंडर्स को रोकता है, चक्रिका कार्यभार को काफी कम करता है और चक्रिका द्रुतिका प्राप्ति दरों में वृद्धि करता है।
• गूगल बिगतालिका, अपाचे एचबेस और अपाचे कैसेंड्रा और पोस्टग्रेएसक्यूएल गैर-उपस्थित पंक्तियों या स्तंभों के लिए चक्रिका लुकअप को कम करने के लिए ब्लूम निस्यंदक का उपयोग करते हैं। बहुमूल्य चक्रिका लुकअप से बचने से आंकड़ाकोष परिप्रश्न संचालन का प्रदर्शन काफी बढ़ जाता है।
• दुर्भावनापूर्ण यूआरएल की पहचान करने के लिए गूगल क्रोम वेब ब्राउज़र पहले ब्लूम निस्यंदक का उपयोग करता था। किसी भी यूआरएल को पहले एक स्थानीय ब्लूम निस्यंदक के प्रतिकूल जांचा गया था और केवल यदि ब्लूम निस्यंदक ने एक सकारात्मक परिणाम लौटाया तो यूआरएल की पूर्ण जांच की गई थी (और उपयोगकर्ता ने चेतावनी दी थी, यदि वह भी सकारात्मक परिणाम लौटाता है)।
• माइक्रोसॉफ्ट बिंग (खोजी यंत्र) अपने खोज सूचकांक, बिटफनल के लिए बहु-स्तरीय श्रेणीबद्ध ब्लूम निस्यंदक का उपयोग करता है। ब्लूम निस्यंदक पिछले बिंग सूचकांक की तुलना में कम लागत प्रदान करते हैं, जो व्युत्क्रमित संचिकाओं पर आधारित था।
• स्क्वीड वेब प्रॉक्सी द्रुतिका, द्रुतिका संकलन के लिए ब्लूम निस्यंदक का उपयोग करता है।
• जब तक ब्लूम निस्यंदक के कार्यान्वयन के साथ गोपनीयता भेद्यता का पता नहीं चला, तब तक बिटकॉइन ने वॉलेट समकालन को गति प्रदान करने के लिए ब्लूम निस्यंदक का उपयोग किया।
• वेंटी पुरालेखी भंडारण प्रणाली पूर्व से संग्रहीत प्रदत्त का पता लगाने के लिए ब्लूम निस्यंदक का उपयोग करती है।
• चक्रण प्रतिरूप जाँचकर्ता बड़ी सत्यापन समस्याओं के लिए सुगम्य स्थिति समष्टि को पथानुसरण करने के लिए ब्लूम निस्यंदक का उपयोग करता है।
• सोपानी विश्लेषणविद्या प्राधार असममित जोड़ को गति प्रदान करने के लिए ब्लूम निस्यंदक का उपयोग करता है, जहां सम्मिलित किए गए प्रदत्त समुच्चय दूसरे की तुलना में काफी बड़ा होता है (जिसे प्रायः ब्लूम संलग्न आंकड़ाकोष साहित्य में कहा जाता है)।
• एग्जिम डाक अंतरण अभिकर्ता (MTA) अपने दर सीमा सुविधा में ब्लूम निस्यंदक का उपयोग करता है।
• उपयोगकर्ता द्वारा पहले पढ़े गए लेखों की अनुशंसा से बचने के लिए माध्यम ब्लूम निस्यंदक का उपयोग करता है।
• इथेरियम खंडचेन पर लॉग को शीघ्रता से खोजने के लिए इथेरियम ब्लूम निस्यंदक का उपयोग करता है।
• ग्राफाना टेम्पो प्रत्येक बैकएंड खंड के लिए ब्लूम निस्यंदक को संग्रहीत करके परिप्रश्न प्रदर्शन के सुधार के लिए ब्लूम निस्यंदक का उपयोग करता है। आपूर्ति किए गए खोज मानदंडों को पूर्ण करने वाले प्रदत्त वाले खंड को निर्धारित करने के लिए इन्हें प्रत्येक परिप्रश्न पर अभिगमन किया जाता है

विकल्प

उत्कृष्ट ब्लूम निस्यंदक $1.44\log _{2}(1/\varepsilon )$ प्रति सम्मिलित की गई समष्टि के द्वयंक का उपयोग करते हैं, जहां $\varepsilon$ ब्लूम निस्यंदक की मिथ्या सकारात्मक दर है। हालाँकि, वह समष्टि जो किसी भी प्रदत्त संरचना के लिए ब्लूम निस्यंदक $\log _{2}(1/\varepsilon )$ प्रति कुंजी के समान भूमिका निभाने के लिए कठोरता से आवश्यक है। इसलिए ब्लूम निस्यंदक समतुल्य इष्टतम प्रदत्त संरचना की तुलना में 44% अधिक समष्टि का उपयोग करते हैं। इसके बजाय, पग एट अल ने एक इष्टतम-समष्टि प्रदत्त संरचना प्रदान की। इसके अतिरिक्त, ब्लूम निस्यंदक के विपरीत, उनकी प्रदत्त संरचना में मिथ्या सकारात्मक दर से स्वतंत्र संदर्भ की निरंतर स्थानीयता होती है, जहां कम मिथ्या सकारात्मक दर $\varepsilon$ होती है, $\log(1/\varepsilon )$ प्रति परिप्रश्न अधिक मेमोरी अभिगमन की ओर ले जाता है। इसके अतिरिक्त, यह ब्लूम निस्यंदक के विपरीत, तत्वों को समष्टि दंड के बिना हटाने की अनुमति प्रदान करता है। इष्टतम समष्टि उपयोग, संदर्भ की निरंतर स्थानीयता और तत्वों को हटाने की क्षमता के समान उन्नत गुण भी फैन एट अल (2014) के कोयल निस्यंदक द्वारा प्रदान किए जाते हैं, जिसका एक मुक्त स्रोत कार्यान्वयन उपलब्ध है।

स्टर्न एंड डिल (1996) ने द्रुतान्वेषण तालिका, द्रुतान्वेषण संघनन पर आधारित एक संभाव्य संरचना का वर्णन करता है, जो डिलिंगर और मैनोलियस (2004बी) ब्लूम निस्यंदक की तुलना में काफी अधिक सटीक पहचानते हैं जब प्रत्येक को इष्टतम रूप से समनुरूप बनाया जाता है। डिलिंगर और मैनोलिओस, हालांकि, बताते हैं कि किसी भी दिए गए ब्लूम निस्यंदक की उचित सटीकता कई प्रकार की परिवर्धन पर अज्ञात आकार की स्थिति रिक्त समष्टि की संभावित गणना के लिए आकर्षक बनाती है। द्रुतान्वेषण संघनन, इसलिए आकर्षक है जब परिवर्धन की संख्या का सटीक अनुमान लगाया जा सकता है; हालाँकि, सॉफ़्टवेयर में बहुत तीव्र होने के बावजूद, द्रुतान्वेषण संघनन सबसे खराब स्थिति वाले रैखिक अभिगमन समय के कारण हार्डवेयर के लिए खराब रूप से अनुकूल है।

पुट्ज़े, सैंडर्स एंड सिंगलर (2007) ने ब्लूम निस्यंदक के कुछ रूपों का अध्ययन किया है जो उत्कृष्ट ब्लूम निस्यंदक की तुलना में या तो तीव्र हैं या कम स्थान का उपयोग करते हैं। तीव्र संस्करण का मूल विचार संसाधक की मेमोरी द्रुतिका खंड (सामान्यतः 64 बाइट) के समान आकार वाले एक या दो खंड में प्रत्येक कुंजी से जुड़े k द्रुतान्वेषण मान का पता लगाना है। यह संभवतः संभावित मेमोरी द्रुतिका मिस की संख्या को कम करके प्रदर्शन में सुधार करेगा। हालांकि प्रस्तावित भिन्नरूप में उत्कृष्ट ब्लूम निस्यंदक की तुलना में लगभग 32% अधिक स्थान का उपयोग करने की असुविधा है।

समष्टि कुशल संस्करण एकल द्रुतान्वेषण फलन का उपयोग करने पर निर्भर करता है जो प्रत्येक कुंजी के लिए श्रेणी $\left[0,n/\varepsilon \right]$ में एक मान उत्पन्न करता है, जहाँ $\varepsilon$ अनुरोधित मिथ्या सकारात्मक दर है। मानों के अनुक्रम को गोलोम्ब कूटलेखन (या कुछ अन्य संपीड़न प्रविधि) का उपयोग करके एक समष्टि $n\log _{2}(1/\varepsilon )$ द्वयंक पर अधिभोग करने के लिए क्रमबद्ध और संपीड़ित किया जाता है। किसी दी गई कुंजी के लिए ब्लूम निस्यंदक को परिप्रश्न करने के लिए, यह जाँचना पर्याप्त होगा कि क्या इसका संबंधित मान ब्लूम निस्यंदक में संग्रहीत है। प्रत्येक परिप्रश्न के लिए संपूर्ण ब्लूम निस्यंदक को असंपीड़ित करने से यह संस्करण पूर्णतया से अनुपयोगी हो जाएगा। इस समस्या को दूर करने के लिए मानों के अनुक्रम को समान आकार के छोटे खंडों में विभाजित किया जाता है जो अलग-अलग संकुचित होते हैं। परिप्रश्न समय पर केवल आधे खंड को औसतन असंपीड़ित करने की आवश्यकता होगी। विसंपीड़न शिरोपरि के कारण, यह संस्करण उत्कृष्ट ब्लूम निस्यंदक की तुलना में धीमा हो सकता है परन्तु इसकी आपूर्ति इस तथ्य से की जा सकती है कि एकल द्रुतान्वेषण फलन की गणना करने की आवश्यकता है।

उत्कृष्ट ब्लूम निस्यंदक का एक अन्य विकल्प कोयल निस्यंदक है, जो कोयल द्रुतान्वेषण के समष्टि-कुशल रूपों पर आधारित है। इस स्थिति में, एक द्रुतान्वेषण तालिका का निर्माण किया जाता है, जिसमें न तो कुंजियाँ होती हैं और न ही मान, परन्तु कुंजियों के छोटे अंगुलि छाप (छोटे द्रुतान्वेषण) होते हैं। यदि कुंजी को देखने से मिलान करने वाला अंगुलि छाप मिलता है, तो कुंजी संभवतः समुच्चय में है। कोयल निस्यंदक की एक उपयोगी गुणधर्म यह है कि वे अद्यतन करने योग्य हैं; प्रविष्टियों को गतिशील रूप से जोड़ा जा सकता है (द्रुतान्वेषण तालिका पूर्ण होने के कारण विफलता की एक छोटी संभाव्यता के साथ) और हटा दी गई।

ग्राफ एंड लेमायर (2020) ने एक एक्सर निस्यंदक नामक एक दृष्टिकोण का वर्णन करता है, जहाँ वे एक विशेष प्रकार की उत्तम द्रुतान्वेषण तालिका में अंगुलि छाप संग्रहीत करते हैं, एक निस्यंदक का निर्माण करते हैं जो अधिक मेमोरी कुशल ($1.23\log _{2}(1/\varepsilon )$ द्वयंक प्रति कुंजी) और ब्लूम या कोयल निस्यंदक की तुलना में तीव्र है (समय की बचत इस तथ्य से होती है कि एक लुकअप के लिए बिल्कुल तीन मेमोरी अभिगम की आवश्यकता होती है, जो सभी समानांतर में निष्पादित हो सकते हैं)। हालांकि, ब्लूम और कोयल निस्यंदक की तुलना में निस्यंदक निर्माण अधिक जटिल है और निर्माण के बाद समुच्चय को संशोधित करना संभव नहीं है।

विस्तारण और अनुप्रयोग

ब्लूम निस्यंदक के 60 से अधिक प्रकार हैं, क्षेत्र के कई सर्वेक्षण और अनुप्रयोगों का एक सतत मंथन (देखें, उदाहरण के लिए, लुओ, एट अल ) हैं। मूल प्रदत्त संरचना और उसके दर्शन के उल्लंघन या विभाजित होने के लिए कुछ संस्करण मूल प्रस्ताव से पर्याप्त रूप से भिन्न हैं।यादृच्छिक अनुमान, संपीडन संवेदन और स्थानीय संवेदनशील द्रुतान्वेषण पर अन्य कार्य के साथ ब्लूम निस्यंदक को एकीकृत करने वाला एक प्रतिपादन किया जाना शेष है (हालांकि, तंत्रिका विज्ञान से प्रेरित एक प्रयास के लिए दासगुप्ता, एट अल देखें) )।

द्रुतिका निस्यंदन

File:BloomFilterDisk.png

360 x 0 पीएक्स

सामग्री वितरण संजाल उन्नत प्रदर्शन और विश्वसनीयता के साथ उपयोगकर्ताओं को द्रुतिका और वेब सामग्री प्रदान करने के लिए विश्व भर में वेब द्रुतिका परिनियोजित करते हैं। ब्लूम निस्यंदक का एक प्रमुख अनुप्रयोग यह है कि इन वेब द्रुतिका में कौन से वेब वस्तु को संग्रहीत करना है, यह कुशलतापूर्वक निर्धारित करने में उनका उपयोग होता है। एक विशिष्ट वेब द्रुतिका से अभिगम किए गए लगभग तीन-चौथाई यूआरएल "वन-हिट-वंडर्स" हैं जो उपयोगकर्ताओं द्वारा केवल एक बार अभिगम किए जाते हैं और फिर कभी नहीं। वेब द्रुतिका में वन-हिट-वंडर्स को संग्रहीत करने के लिए चक्रिका संसाधनों की स्पष्ट रूप से अपव्ययी है, क्योंकि उन्हें फिर कभी अभिगमन नहीं किया जाएगा। वन-हिट-वंडर्स को द्रुतिका से बचाने के लिए, उपयोगकर्ताओं द्वारा अभिगमन किए जाने वाले सभी यूआरएल का पथानुसरण रखने के लिए ब्लूम निस्यंदक का उपयोग किया जाता है। एक वेब वस्तु को तभी द्रुतिका किया जाता है जब इसे कम-से-कम एक बार पहले अभिगमन किया गया हो, अर्थात वस्तु को उसके दूसरे अनुरोध पर द्रुतिका किया गया हो। इस तरीके से ब्लूम निस्यंदक का उपयोग चक्रिका लेखन कार्यभार को काफी कम कर देता है, क्योंकि अधिकांश वन-हिट-वंडर्स चक्रिका द्रुतिका में नहीं लिखे जाते हैं। इसके अतिरिक्त, वन-हिट-वंडर्स को निस्यंदक करने से चक्रिका पर द्रुतिका स्थान की बचत होती है, जिससे द्रुतिका हिट दर बढ़ जाती है।

एक परिमित ब्रह्मांड में मिथ्या सकारात्मकता से बचना

चुंबन एट अल ने ब्लूम निस्यंदक के लिए एक नए निर्माण का वर्णन किया गया है जो मिथ्या अपवर्जित के विशिष्ट गैर-अस्तित्व के अतिरिक्त मिथ्या सकारात्मकता से बचाता है। निर्माण एक परिमित ब्रह्मांड पर अनुप्रयुक्त होता है जिसमें से समुच्चय तत्व लिए जाते हैं। यह एपस्टीन, गुडरिक और हिर्शबर्ग द्वारा उपस्थित गैर-अनुकूली संयोजी समूह परीक्षण योजना पर निर्भर करता है। विशिष्ट ब्लूम निस्यंदक के विपरीत, तत्वों को नियतात्मक, तीव्र और सरल-से-गणना कार्यों के माध्यम से एक द्वयंक सरणी में द्रुतान्वेषण किया जाता है। अधिकतम समुच्चय आकार जिसके लिए मिथ्या सकारात्मकता से पूर्णतया से बचा जाता है, ब्रह्मांड के आकार का एक फलन है और आवंटित स्मृति की मात्रा से नियंत्रित होता है।

वैकल्पिक रूप से, प्रारंभिक ब्लूम निस्यंदक मानक तरीके से बनाया जा सकता है और फिर, एक परिमित और विनयपूर्वक-गणनीय कार्यक्षेत्र के साथ, सभी मिथ्या सकारात्मकताओं को व्यापक रूप से पाया जा सकता है और फिर उस सूची से एक दूसरा ब्लूम निस्यंदक बनाया जा सकता है; दूसरे निस्यंदक में मिथ्या सकारात्मकताओं को इसी तरह तीसरे और इसी तरह से नियंत्रित किया जाता है। जैसा कि ब्रह्मांड परिमित है और मिथ्या सकारात्मकता का समुच्चय प्रत्येक चरण के साथ दृढ़ता से सन्कुचित है, इस प्रक्रिया के परिणामस्वरूप ब्लूम निस्यंदक का एक सीमित सोपान होता है जो (इस संवृत्त, परिमित कार्यक्षेत्र पर) केवल वास्तविक सकारात्मक और वास्तविक नकारात्मक का उत्पादन करेगा। निस्यंदक सोपान में सदस्यता की जाँच करने के लिए, प्रारंभिक निस्यंदक से परिप्रश्न किया जाता है और यदि परिणाम सकारात्मक होता है और इसी तरह दूसरे निस्यंदक से परामर्श किया जाता है, इस निर्माण का उपयोग सीआरलाइट में किया जाता है, वेब पीकेआई के लिए एक प्रस्तावित प्रमाणपत्र निरस्तीकरण स्थिति वितरण क्रियाविधि और उपस्थिता प्रमाणपत्रों के समुच्चय को संवृत्त करने के लिए प्रमाणपत्र पारदर्शिता का उपयोग किया जाता है।

ब्लूम निस्यंदक की गणना

Main article: ब्लूम फिल्टर की गणना

गणना निस्यंदक, ब्लूम निस्यंदक को नए सिरे से बनाए बिना विलोपन संचालन को अनुप्रयुक्त करने का एक तरीका प्रदान करते हैं। एक गणना निस्यंदक में, सरणि स्थिति (समूह) को एकल द्वयंक से बहु-द्वयंक गणक तक बढ़ाया जाता है। वास्तव में, नियमित ब्लूम निस्यंदक को एक द्वयंक के समूह आकार के साथ गणना निस्यंदक के रूप में माना जा सकता है। गणना निस्यंदक फैन एट अल (2000) द्वारा द्वारा प्रस्तुत किए गए थे।

अंतर्वेशन संचालन को समूह के मान को बढ़ाने के लिए बढ़ाया जाता है और लुकअप संचालन यह जाँचता है कि प्रत्येक आवश्यक समूह गैर-शून्य है। इसके पश्चात, विलोपन संचालन में संबंधित समूह में से प्रत्येक के मान को कम करना सम्मिलित है।

समूहों का अंकगणितीय अतिप्रवाह एक समस्या है और इस स्थिति को दुर्लभ बनाने के लिए समूहों को पर्याप्त रूप से बड़ा होना चाहिए। यदि ऐसा होता है तो ब्लूम निस्यंदक के गुणों को बनाए रखने के लिए वृद्धि और कमी के संचालन को समूहों समुच्चय को अधिकतम संभव मान पर छोड़ देना चाहिए।

गणकों का आकार सामान्यतः 3 या 4 द्वयंक होता है। इसलिए गणना ब्लूम निस्यंदक स्थैतिक ब्लूम निस्यंदक की तुलना में 3 से 4 गुना अधिक स्थान का उपयोग करते हैं। इसके विपरीत, पाघ, पाघ एंड राव (2005) और फैन एट अल (2014) की प्रदत्त संरचनाएं है। विलोपन की अनुमति भी देता है, परन्तु स्थिर ब्लूम निस्यंदक की तुलना में कम स्थान का उपयोग करता है।

गणना निस्यंदक के साथ एक और विवाद सीमित मापनीयता है क्‍योंकि गणना ब्‍लूम निस्यंदक तालिका को विस्‍तारित नहीं किया जा सकता है, निस्यंदक में एक साथ संग्रहित की जाने वाली कुंजियों की अधिकतम संख्‍या पूर्व से ज्ञात होनी चाहिए। एक बार जब तालिका की परिकल्पित की गई क्षमता पार हो जाती है, तो मिथ्या सकारात्मक दर तीव्रता से बढ़ेगी क्योंकि अधिक कुंजियाँ डाली जाती हैं।

बोनोमी एट अल(2006) ने d-बाएँ द्रुतान्वेषण पर आधारित एक प्रदत्त संरचना प्रस्तुत की जो कार्यात्मक रूप से समतुल्य है परन्तु ब्लूम निस्यंदक की गणना के रूप में लगभग आधी स्थान का उपयोग करती है। इस प्रदत्त संरचना में मापनीयता समस्या उत्पन्न नहीं होती है। एक बार परिकल्पित की गई क्षमता पार हो जाने के पश्चात, कुंजियों को द्विक आकार की एक नई द्रुतान्वेषण तालिका में पुनः डाला जा सकता है।

पुट्ज़े, सैंडर्स एंड सिंगलर (2007) द्वारा समष्टि कुशल संस्करण का उपयोग अंतर्वेशन और विलोपन का समर्थन करके गणना निस्यंदक अनुप्रयुक्त करने के लिए भी उपयोग किया जा सकता है।

रोटेनस्ट्रेइच, कनिज़ो और केस्लासी (2012) ने चर वृद्धि के आधार पर एक नई सामान्य पद्धति प्रस्तावित की, जो अभी भी विलोपन का समर्थन करते हुए, ब्लूम निस्यंदक और उनके भिन्नरूप की गणना की मिथ्या सकारात्मक संभाव्यता में काफी सुधार करता है। ब्लूम निस्यंदक की गणना के विपरीत, प्रत्येक तत्व अंतर्वेशन पर, द्रुतान्वेषण किए गए गणकों को एक इकाई वृद्धि के बजाय एक द्रुतान्वेषण चर वृद्धि द्वारा बढ़ाया जाता है। किसी तत्व को परिप्रश्न करने के लिए, गणकों के सटीक मानों पर विचार किया जाता है, न कि केवल उनकी सकारात्मकता पर। यदि किसी गणक मान द्वारा दर्शायी गई राशि को परिप्रश्न किए गए तत्व के लिए संबंधित चर वृद्धि से नहीं बनाया जा सकता है, तो एक नकारात्मक उत्तर को परिप्रश्न में वापस किया जा सकता है।

किम एट अल। (2019) किम एट अल (2019) दर्शाता है कि गणना ब्लूम निस्यंदक का मिथ्या सकारात्मकता k=1 से परिभाषित बिंदु $k_{opt}$तक घटता है और सकारात्मक अनंत तक $k_{opt}$ से बढ़ता है। गणना सीमा के एक फलन $k_{opt}$ के रूप में पाता है।

विकेंद्रीकृत एकत्रीकरण

कुल कार्यों की पूर्णतया से विकेंद्रीकृत संगणना करने के लिए ब्लूम निस्यंदक को वितरित प्रदत्त संरचनाओं में व्यवस्थित किया जा सकता है। विकेंद्रीकृत एकत्रीकरण इस उद्देश्य के लिए केंद्रीकृत गणना इकाई को सम्मिलित किए बिना वितरित संजाल के प्रत्येक बिंदु में स्थानीय रूप से सामूहिक माप उपलब्ध कराता है।

वितरित ब्लूम निस्यंदक

File:DistributedBloomFilterExample.png

मिथ्या सकारात्मक दर के साथ प्रतिलिपि का पता लगाने के लिए वितरित सिंगल शॉट ब्लूम निस्यंदक: 6 तत्वों को 3 पीई में वितरित किया जाता है, प्रत्येक की लंबाई 4 होती है। पहले संचार चरण के पर्यन्त पीई 1 द्रुतान्वेषण '2' को दो बार प्राप्त करता है और इसे वापस भेजता है पीई 2 या 3, इस पर निर्भर करता है कि इसे बाद में किसने भेजा। पीई जो द्रुतान्वेषण '2' प्राप्त करता है, फिर उस द्रुतान्वेषण वाले तत्व की खोज करता है और इसे संभावित प्रतिलिपि के रूप में चिह्नित करता है।

समानांतर सहभाजी-अभाव यंत्रो में उपस्थित बहुखंडीय प्रसंस्करण घटक (PE) का लाभ उठाने के लिए समानांतर ब्लूम निस्यंदक अनुप्रयुक्त किए जा सकते हैं। समानांतर ब्लूम निस्यंदक के लिए मुख्य बाधाओं में से एक अनियंत्रित प्रदत्त का संगठन और संचार है, जो सामान्य रूप से, प्रारंभ में या वर्ग अंतर्वेशन पर सभी पीई पर समान रूप से वितरित किया जाता है। प्रदत्त को अनुक्रम करने के लिए दो दृष्टिकोणों का उपयोग किया जा सकता है, या तो प्रत्येक पीई पर संग्रहीत किए जा रहे सभी प्रदत्त पर ब्लूम निस्यंदक का परिणाम होता है, जिसे ब्लूम निस्यंदक की प्रतिकृति कहा जाता है, या ब्लूम निस्यंदक को सभी प्रदत्त को समान भागों में विभाजित किया जाता है, प्रत्येक पीई इसका एक भाग संग्रहीत करता है। दोनों दृष्टिकोणों के लिए एक एकस्थितिक ब्लूम निस्यंदक का उपयोग किया जाता है जो संचार मात्रा को कम करने के लिए केवल एक द्रुतान्वेषण की गणना करता है, जिसके परिणामस्वरूप प्रति तत्व एक फ़्लिप द्वयंक होता है।

वितरित ब्लूम निस्यंदक पहले उनके स्थानीय पीई पर सभी तत्वों को द्रुतान्वेषण करके और फिर उन्हें स्थानीय स्तर पर द्रुतान्वेषण द्वारा वर्गीकृत करके प्रारंभ किया जाता है। यह रैखिक समय में किया जा सकता है उदाहरण- समूह वर्गीकृत और स्थानीय प्रतिलिपि संसूचन की भी अनुमति प्रदान करता है। वर्गीकरण का उपयोग प्रत्येक समूह के लिए एक ब्लूम निस्यंदक बनाने के लिए विभाजक के रूप में उनके निर्दिष्ट किए गए पीई के साथ द्रुतान्वेषण को समूहित करने के लिए किया जाता है। इन ब्लूम निस्यंदक को संकेतीकरण करने के पश्चात उदाहरण- गोलोम्ब कूटलेखन प्रत्येक ब्लूम निस्यंदक को पीई को वेष्टक के रूप में भेजा जाता है जो द्रुतान्वेषण मानों के लिए उत्तरदायी होता है जहां इसे डाला जाता है। एक पीई पी मानों के मध्य सभी द्रुतान्वेषण $p*(s/|{\text{PE}}|)$ और $(p+1)*(s/|{\text{PE}}|)$ के लिए उत्तरदायी है, जहां s सभी प्रदत्त पर ब्लूम निस्यंदक का कुल आकार है क्योंकि प्रत्येक तत्व केवल एक बार द्रुतान्वेषण को किया जाता है और इसलिए केवल एक द्वयंक व्यवस्थित किया जाता है, यह जांचने के लिए कि क्या कोई तत्व ब्लूम निस्यंदक में डाला गया था, तत्व के द्रुतान्वेषण मान के लिए उत्तरदायी पीई को ही संचालित करने की आवश्यकता है। एकल अंतर्वेशन संचालन को कुशलता से भी किया जा सकता है क्योंकि ब्लूम निस्यंदक की प्रतिकृति करने की तुलना में केवल एक पीई के ब्लूम निस्यंदक को परिवर्तित करना पड़ता है, जहां प्रत्येक पीई को अपने ब्लूम निस्यंदक को अद्यतन करना होगा। वैश्विक ब्लूम निस्यंदक को प्रत्येक पीई पर अलग से संग्रहीत करने के बजाय सभी पीई पर वितरित करके ब्लूम निस्यंदक का आकार बहुत बड़ा हो सकता है, जिसके परिणामस्वरूप बड़ी क्षमता और कम मिथ्या सकारात्मक दर होती है। वितरित ब्लूम निस्यंदक का उपयोग प्रतिलिपि संसूचन कलन विधि को सबसे 'अद्वितीय' तत्वों को निस्यंदन करके सुधारने के लिए किया जा सकता है। इनकी गणना केवल तत्वों के द्रुतान्वेषण को संप्रेषित करके की जा सकती है, न कि स्वयं उन तत्वों को जो मात्रा में बहुत बड़े हैं और उन्हें समुच्चय से हटाकर, बाद में उपयोग किए जाने वाले प्रतिलिपि संसूचन कलन विधि के कार्यभार को कम कर सकते हैं।

द्रुतान्वेषण के संचार के पर्यन्त पीई द्वयंक की खोज करते हैं जो एक से अधिक प्राप्त वेष्टको में व्यवस्थित होते हैं, क्योंकि इसका अर्थ यह होगा कि दो तत्वों में एक ही द्रुतान्वेषण था और इसलिए प्रतिलिपि हो सकते हैं। यदि ऐसा होता है तो एक संदेश जिसमें द्वयंक का सूचकांक होता है, जो उस तत्व का द्रुतान्वेषण भी होता है जो प्रतिलिपि हो सकता है, पीई को भेजा जाता है जिसने समुच्चय द्वयंक के साथ एक वेष्टक भेजा था। यदि एक प्रेषक द्वारा एक ही पीई को कई सूचकांक भेजे जाते हैं तो सूचकांकों को भी संकेतीकरण करना लाभदायक हो सकता है। सभी तत्व जिनके द्रुतान्वेषण को वापस नहीं भेजा गया था, उन्हें अब प्रतिलिपि नहीं होने की प्रत्याभूति दी गई है और आगे मूल्यांकन नहीं किया जाएगा, शेष तत्वों के लिए एक पुनर्विभाजन कलन विधि का उपयोग किया जा सकता है। पहले वे सभी तत्व जिनका द्रुतान्वेषण मान वापस भेजा गया था, पीई को भेजे जाते हैं, जिसके लिए उनका द्रुतान्वेषण उत्तरदायी है। कोई भी तत्व और उसका प्रतिलिपि अब उसी पीई पर होने की प्रत्याभूति है। दूसरे चरण में प्रत्येक पीई प्राप्त तत्वों पर प्रतिलिपि पहचान के लिए अनुक्रमिक कलन विधि का उपयोग करता है, जो प्रारंभिक तत्वों की मात्रा का केवल एक अंश है। प्रतिलिपि के लिए मिथ्या सकारात्मक दर की अनुमति देकर, संचार की मात्रा को और कम किया जा सकता है क्योंकि पीई को प्रतिलिपि द्रुतान्वेषण वाले तत्वों को भेजने की आवश्यकता नहीं है और इसके बजाय प्रतिलिपि द्रुतान्वेषण वाले किसी भी तत्व को प्रतिलिपि के रूप में चिह्नित किया जा सकता है। परिणामस्वरूप, प्रतिलिपि संसूचन के लिए मिथ्या सकारात्मक दर प्रयुक्त ब्लूम निस्यंदक की मिथ्या सकारात्मक दर के समान होती है।

प्रत्येक निस्यंदन चरण में द्रुतान्वेषण फलन को परिवर्तित कर सबसे 'अद्वितीय' तत्वों को निस्यंदक करने की प्रक्रिया को कई बार दोहराया जा सकता है। यदि केवल एक निस्यंदन चरण का उपयोग किया जाता है, तो उसे एक छोटी मिथ्या सकारात्मक दर संग्रहित करनी होती है, हालाँकि यदि निस्यंदन चरण को एक बार दोहराया जाता है, तो पहला चरण एक उच्च मिथ्या सकारात्मक दर की अनुमति दे सकता है, जबकि बाद वाले के पास उच्च होता है, परन्तु कम तत्वों पर भी कार्य करता है। जितने पहले के निस्यंदन चरण द्वारा पहले ही हटा दिए गए हैं। जबकि दो से अधिक पुनरावृत्तियों का उपयोग संचार की मात्रा को और कम कर सकता है यदि एक समुच्चय में प्रतिलिपि की संख्या कम है, तो अतिरिक्त जटिलताओं के लिए भुगतान कम है।

ब्लूम निस्यंदक की नकल करने वाले अपने प्रदत्त को प्रलाप के लिए एक प्रसिद्ध अतिविम कलन विधि का उपयोग करके व्यवस्थित करते हैं, उदाहरण के लिए पहले प्रत्येक पीई सभी स्थानीय तत्वों पर ब्लूम निस्यंदक की गणना करता है और इसे संग्रहीत करता है। एक पाश को दोहराते हुए जहां प्रत्येक चरण में पीई अपने स्थानीय ब्लूम निस्यंदक को आयाम i पर भेजते हैं और ब्लूम निस्यंदक को अपने स्थानीय ब्लूम निस्यंदक के साथ आयाम पर प्राप्त करते हैं, प्रत्येक पुनरावृत्ति में प्रत्येक ब्लूम निस्यंदक में सम्मिलित तत्वों को दोगुना करना संभव है। ब्लूम निस्यंदक भेजने और प्राप्त करने के पश्चात, $\log |{\text{PE}}|$ आयाम प्रत्येक पीई में सभी तत्वों पर वैश्विक ब्लूम निस्यंदक होता है।

ब्लूम निस्यंदक की प्रतिकृति तब अधिक कुशल होती है जब प्रश्नों की संख्या ब्लूम निस्यंदक में सम्मिलित तत्वों की संख्या से बहुत अधिक होती है, वितरित ब्लूम निस्यंदक की तुलना में लाभ - अलाभ बिंदु लगभग बाद में $|{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|$ तक, $f^{\text{+}}$ के साथ ब्लूम निस्यंदक की मिथ्या सकारात्मक दर के रूप में पहुँचते है।

प्रदत्त तुल्यकालन

बायर्स एट अल के रूप में अनुमानित प्रदत्त तुल्यकालन के लिए ब्लूम निस्यंदक का उपयोग किया जा सकता है। गणना ब्लूम निस्यंदक का उपयोग दो समुच्चयों के मध्य अंतर की संख्या का अनुमान लगाने के लिए किया जा सकता है और इस दृष्टिकोण का वर्णन अग्रवाल और ट्रेचेनबर्ग (2006) में किया गया है।

अभिस्रवण प्रदत्त के लिए ब्लूम निस्यंदक

ब्लूम निस्यंदक को अभिस्रवण प्रदत्त के संदर्भ में अनुकूलित किया जा सकता है। उदाहरण के लिए, देंग और रफ़ी (2006) ने प्रस्तावित स्थिर ब्लूम निस्यंदक, जिसमें एक गणना ब्लूम निस्यंदक होता है, जहाँ एक नए तत्व का अंतर्वेशन संबंधित गणकों को एक मान पर समुच्चय करता है c, और उसके बाद केवल एक निश्चित राशि s काउंटर 1 से कम हो जाते हैं, इसलिए मेमोरी में ज्यादातर हाल के तत्वों के बारे में जानकारी होती है (सहजता से, कोई यह मान सकता है कि एसबीएफ के भीतर एक तत्व का जीवनकाल N काउंटर आसपास है $c{\tfrac {s}{N}}$). एजिंग ब्लूम निस्यंदक एक अन्य समाधान है, जिसमें दो ब्लूम निस्यंदक होते हैं, जिनमें से प्रत्येक कुल उपलब्ध मेमोरी का आधा भाग घेरता है: जब एक निस्यंदक भर जाता है, तो दूसरा निस्यंदक मिटा दिया जाता है और नए तत्वों को इस नए अपूरित निस्यंदक में जोड़ दिया जाता है। हालाँकि, दिखाया गया है निस्यंदक के बाद कोई फर्क नहीं पड़ता n अंतर्वेशन, मिथ्या सकारात्मक का योग $FP$ और झूठा नकारात्मक $FN$ संभाव्यताओं से नीचे घिरा है ${\textstyle \scriptstyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$ जहाँ L सभी संभावित तत्वों की मात्रा है (वर्णमाला का आकार), m स्मृति आकार (द्वयंक में), मानते हुए $n>m$. यह परिणाम दर्शाता है कि के लिए L काफी बड़ा और n अनंत तक जा रहा है, फिर निचली सीमा में परिवर्तित हो जाता है $FP+FN=1$, जो एक यादृच्छिक निस्यंदक का विशिष्ट संबंध है। इसलिए, पर्याप्त अंतर्वेशन के बाद, और यदि स्मृति में संग्रहीत करने के लिए वर्णमाला बहुत बड़ी है (जो कि संभाव्य निस्यंदक के संदर्भ में माना जाता है), निस्यंदक के लिए यादृच्छिकता से उन्नत प्रदर्शन करना असंभव है। इस परिणाम को पूरी धारा के बजाय केवल एक स्लाइडिंग विंडो पर संचालित करने के लिए निस्यंदक की अपेक्षा करके लीवरेज किया जा सकता है। इस स्थिति में, प्रतिपादक {{mvar|n}उपरोक्त सूत्र में } द्वारा प्रतिस्थापित किया गया है w, जो एक सूत्र देता है जो 1 से विचलित हो सकता है, यदि w बहुत छोटा नहीं है।

ब्लूमियर निस्यंदक

Chazelle et al. (2004) ने ब्लूम निस्यंदक का एक सामान्यीकरण तैयार किया है जो एक साहचर्य सरणी को अनुप्रयुक्त करते हुए, सम्मिलित किए गए प्रत्येक तत्व के साथ एक मान को जोड़ सकता है। ब्लूम निस्यंदक की तरह, ये संरचनाएं मिथ्या सकारात्मकता की एक छोटी संभाव्यता को स्वीकार करके एक छोटी सी जगह ओवरहेड प्राप्त करती हैं। ब्लूमियर निस्यंदक के स्थिति में, एक मिथ्या सकारात्मक को एक परिणाम के रूप में परिभाषित किया जाता है जब कुंजी मानचित्र में नहीं होती है। मानचित्र में उपस्थित कुंजी के लिए मानचित्र कभी भी गलत मान नहीं लौटाएगा।

कॉम्पैक्ट सन्निकटन

Boldi & Vigna (2005) ने ब्लूम निस्यंदक के जाली (आदेश) आधारित सामान्यीकरण का प्रस्ताव रखा। एक कॉम्पैक्ट सन्निकटन प्रत्येक कुंजी को एक जाली के एक तत्व से जोड़ता है (मानक ब्लूम निस्यंदक बूलियन दो-तत्व जाली का मामला है)। द्वयंक सरणी के बजाय, उनके पास जाली तत्वों की सरणी होती है। कुंजी और जाली के एक तत्व के मध्य एक नया जुड़ाव जोड़ते समय, वे जाली तत्व के साथ कुंजी से जुड़े k सरणी समष्टिों की वर्तमान सामग्री की अधिकतम गणना करते हैं। किसी कुंजी से संबद्ध मान को पढ़ते समय, वे कुंजी से संबद्ध k समष्टिों में पाए जाने वाले न्यूनतम मानों की गणना करते हैं। परिणामी मान मूल मान के ऊपर से अनुमानित होता है।

समानांतर विभाजित ब्लूम निस्यंदक

यह कार्यान्वयन प्रत्येक द्रुतान्वेषण फलन के लिए एक अलग सरणी का उपयोग करता है। यह विधि अंतर्वेशन और पूछताछ दोनों के लिए समांतर द्रुतान्वेषण गणनाओं की अनुमति देती है।

मापनीय ब्लूम निस्यंदक

Almeida et al. (2007) ने ब्लूम निस्यंदक का एक प्रकार प्रस्तावित किया जो न्यूनतम मिथ्या सकारात्मक संभाव्यता सुनिश्चित करते हुए गतिशील रूप से संग्रहीत तत्वों की संख्या के अनुकूल हो सकता है। यह प्रविधि बढ़ती क्षमता और कड़ी मिथ्या सकारात्मक संभाव्यताओं के साथ मानक ब्लूम निस्यंदक के अनुक्रम पर आधारित है, ताकि यह सुनिश्चित किया जा सके कि सम्मिलित किए जाने वाले तत्वों की संख्या की परवाह किए बिना अधिकतम मिथ्या सकारात्मक संभाव्यता पहले से निर्धारित की जा सकती है।

समष्टििक ब्लूम निस्यंदक

समष्टििक ब्लूम निस्यंदक (एसबीएफ) मूल रूप से किसके द्वारा प्रस्तावित किया गया था? Palmieri, Calderoni & Maio (2014) विशेष रूप से समष्टि सूचना गोपनीयता के लिए क्रिप्टोग्राफ़िक प्रोटोकॉल के संदर्भ में समष्टि जानकारी संग्रहीत करने के लिए डिज़ाइन की गई प्रदत्त संरचना के रूप में। हालांकि, एसबीएफ की मुख्य विशेषता एक ही प्रदत्त संरचना में कई समुच्चयों को संग्रहीत करने की उनकी क्षमता है, जो उन्हें कई अलग-अलग एप्लिकेशन परिदृश्यों के लिए उपयुक्त बनाती है। एक विशिष्ट समुच्चय के लिए एक तत्व की सदस्यता को पूछताछ की जा सकती है, और मिथ्या सकारात्मक संभाव्यता समुच्चय पर निर्भर करती है: निर्माण के पर्यन्त निस्यंदक में दर्ज किए जाने वाले पहले समुच्चयों में अंत में दर्ज किए गए समुच्चयों की तुलना में उच्च मिथ्या सकारात्मक संभाव्यताएं होती हैं। यह गुणधर्म समुच्चय की प्राथमिकता की अनुमति देती है, जहां अधिक महत्वपूर्ण तत्वों वाले समुच्चय को संरक्षित किया जा सकता है।

स्तरित ब्लूम निस्यंदक

एक स्तरित ब्लूम निस्यंदक में कई ब्लूम निस्यंदक परतें होती हैं। स्तरित ब्लूम निस्यंदक यह जाँचने की अनुमति देता है कि कितनी बार पद में कितनी परतें हैं, यह जाँच कर ब्लूम निस्यंदक में एक पद को कितनी बार जोड़ा गया था। एक स्तरित ब्लूम निस्यंदक के साथ एक चेक संचालन सामान्य रूप से सबसे गहरी परत संख्या लौटाएगा जिसमें पद पाया गया था।

{{Anchor|ATTENUATED}क्षीणित ब्लूम निस्यंदक

File:AttenuatedBloomFilter2.png

क्षीणित ब्लूम निस्यंदक उदाहरण: प्रतिरूप 11010 के लिए खोजें, बिंदु n1 से प्रारंभ।

गहराई डी के एक दुर्बल ब्लूम निस्यंदक को डी सामान्य ब्लूम निस्यंदक की एक सरणी के रूप में देखा जा सकता है। एक संजाल में सेवा की खोज के संदर्भ में, प्रत्येक बिंदु स्थानीय रूप से नियमित और क्षीण ब्लूम निस्यंदक को संग्रहीत करता है। नियमित या स्थानीय ब्लूम निस्यंदक इंगित करता है कि बिंदु द्वारा कौन सी सेवाएं प्रदान की जाती हैं। स्तर I का क्षीणित निस्यंदक इंगित करता है कि कौन सी सेवाएँ उन बिंदु्स पर पाई जा सकती हैं जो वर्तमान बिंदु से i-hops दूर हैं। i-th मान बिंदु से दूर i-hops बिंदु्स के लिए स्थानीय ब्लूम निस्यंदक का एक संघ लेकर बनाया गया है।

आइए एक उदाहरण के रूप में नीचे दिए गए ग्राफ़ पर दिखाए गए एक छोटे से संजाल को लें। कहते हैं कि हम एक सेवा A की खोज कर रहे हैं जिसकी आईडी 0,1, और 3 (प्रतिरूप 11010) द्वयंक के लिए द्रुतान्वेषण है। n1 बिंदु को प्रारंभिक बिंदु होने दें। सबसे पहले, हम जाँचते हैं कि सेवा A को n1 द्वारा उसके स्थानीय निस्यंदक की जाँच करके प्रस्तुत किया जाता है या नहीं। चूंकि प्रतिरूप मेल नहीं खाते हैं, इसलिए हम यह निर्धारित करने के लिए दुर्बल ब्लूम निस्यंदक की जांच करते हैं कि अगला हॉप कौन सा बिंदु होना चाहिए। हम देखते हैं कि n2 सेवा A की प्रस्तुति नहीं करता है, परन्तु यह करने वाले बिंदु्स के रास्ते पर है। इसलिए, हम n2 पर जाते हैं और उसी प्रक्रिया को दोहराते हैं। हम जल्दी से पाते हैं कि n3 सेवा प्रदान करता है, और इसलिए गंतव्य स्थित है।

कई परतों वाले क्षीणित ब्लूम निस्यंदक का उपयोग करके, एक से अधिक हॉप दूरी पर सेवाओं की खोज की जा सकती है, जबकि ब्लूम निस्यंदक की संतृप्ति से बचने के लिए स्रोतों द्वारा निर्धारित द्वयंक को क्षीण (समष्टिांतरित) करके दूर किया जा सकता है।

रासायनिक संरचना की खोज

ब्लूम निस्यंदक का उपयोग प्रायः बड़े रासायनिक संरचना आंकड़ाकोष (रासायनिक समानता देखें) को खोजने के लिए किया जाता है। सबसे सरल स्थिति में, निस्यंदक में जोड़े गए तत्व (इस क्षेत्र में एक अंगुलि छाप कहा जाता है) अणु में उपस्थित परमाणु संख्याएं हैं, या प्रत्येक परमाणु की परमाणु संख्या और उसके बंधनों की संख्या और प्रकार के आधार पर एक द्रुतान्वेषण है। उपयोगी होने के लिए यह स्थिति बहुत सरल है। अधिकांश उन्नत निस्यंदक भी परमाणु की संख्या, कार्बोक्सिल समूहों जैसे बड़े उप-संरचना सुविधाओं और वलय की संख्या जैसे आलेख गुणों को कूटबद्ध करते हैं। द्रुतान्वेषण-आधारित अंगुलि छाप में, परमाणु और परिबंध गुणों पर आधारित एक द्रुतान्वेषण फलन का उपयोग एक उप-आलेख को पीआरएनजी मूल में परिवर्तित करने के लिए किया जाता है और ब्लूम निस्यंदक में द्वयंक व्यवस्थित करने के लिए पहले निर्गत मान का उपयोग किया जाता है।

आणविक अंगुलि छापों के निशान 1940 के दशक के अंत में छिद्रित पत्रकों पर खोजी गई रासायनिक संरचनाओं की खोज के रूप में प्रारंभ हुए। हालांकि, 1990 के आसपास ऐसा नहीं था कि सूर्य का प्रकाश केमिकल इंफॉर्मेशन सिस्टम्स, इंक. ने पूर्व संगणित तालिका का उपयोग करने के बजाय द्वयंक उत्पन्न करने के लिए एक द्रुतान्वेषण-आधारित पद्धति की शुरुआत की। शब्दकोष दृष्टिकोण के विपरीत, द्रुतान्वेषण विधि उप-संरचनाओं के लिए द्वयंक निर्दिष्ट कर सकती है जो पहले नहीं देखी गई थी। 1990 के दशक की प्रारम्भ में, अंगुलि छाप शब्द को संरचनात्मक कुंजी से अलग माना जाता था, परन्तु तब से यह शब्द अधिकांश आणविक विशेषताओं को सम्मिलित करने के लिए विकसित हो गया है, जिसका उपयोग संरचनात्मक कुंजी, विरल गणना अंगुलि छाप और 3D अंगुलि छाप सहित समानता तुलना के लिए किया जा सकता है। ब्लूम निस्यंदक के विपरीत, सूर्य का प्रकाश द्रुतान्वेषण विधि सुविधा आकार के एक फलन होने के लिए प्रति सुविधा निर्दिष्ट द्वयंक की संख्या की अनुमति देती है, परन्तु सूर्य का प्रकाश-जैसे अंगुलि छाप के अधिकांश कार्यान्वयन प्रति सुविधा द्वयंक की एक निश्चित संख्या का उपयोग करते हैं, जो उन्हें ब्लूम निस्यंदक बनाता है। मूल सूर्य का प्रकाश अंगुलि छाप का उपयोग समानता और पृथक्करण उद्देश्यों दोनों के लिए किया जा सकता है। लोकप्रिय ECFP2 जैसे कई अन्य अंगुलि छाप प्रकारों का उपयोग समानता के लिए किया जा सकता है, परन्तु पृथक्करण के लिए नहीं, क्योंकि उनमें स्थानीय पर्यावरणीय विशेषताएँ सम्मिलित होती हैं, जो स्क्रीन के रूप में उपयोग किए जाने पर गलत नकारात्मक प्रस्तुत करती हैं। भले ही इनका निर्माण एक ही तंत्र के साथ किया गया हो, ये ब्लूम निस्यंदक नहीं हैं क्योंकि इन्हें निस्यंदक करने के लिए उपयोग नहीं किया जा सकता है।

यह भी देखें

• गणना-लघुत्तम रेखांकन
• अभिलक्षण द्रुतान्वेषण
• लघुत्तम द्रुतान्वेषण
• भागफल निस्यंदक
• लुप्ति सूची
• जैव सूचना विज्ञान में ब्लूम निस्यंदक
• सारंग निस्यंदक

संदर्भ

• Agarwal, Sachin; Trachtenberg, Ari (2006), "Approximating the number of differences between remote sets" (PDF), IEEE Information Theory Workshop, Punta del Este, Uruguay: 217, CiteSeerX 10.1.1.69.1033, doi:10.1109/ITW.2006.1633815, ISBN 978-1-4244-0035-5, S2CID 2048278
• Ahmadi, Mahmood; Wong, Stephan (2007), "A Cache Architecture for Counting Bloom Filters", 15th international Conference on Networks (ICON-2007), p. 218, CiteSeerX 10.1.1.125.2470, doi:10.1109/ICON.2007.4444089, ISBN 978-1-4244-1229-7, S2CID 2967865
• Almeida, Paulo; Baquero, Carlos; Preguica, Nuno; Hutchison, David (2007), "Scalable Bloom Filters" (PDF), Information Processing Letters, 101 (6): 255–261, doi:10.1016/j.ipl.2006.10.007, hdl:1822/6627
• Apache Software Foundation (2012), "11.6. Schema Design", The Apache HBase Reference Guide, Revision 0.94.27
• Bloom, Burton H. (1970), "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 13 (7): 422–426, CiteSeerX 10.1.1.641.9096, doi:10.1145/362686.362692, S2CID 7931252
• Blustein, James; El-Maazawi, Amal (2002), "optimal case for general Bloom filters", Bloom Filters — A Tutorial, Analysis, and Survey, Dalhousie University Faculty of Computer Science, pp. 1–31
• Boldi, Paolo; Vigna, Sebastiano (2005), "Mutable strings in Java: design, implementation and lightweight text-search algorithms", Science of Computer Programming, 54 (1): 3–23, doi:10.1016/j.scico.2004.05.003
• Bonomi, Flavio; Mitzenmacher, Michael; Panigrahy, Rina; Singh, Sushil; Varghese, George (2006), "An Improved Construction for Counting Bloom Filters", Algorithms – ESA 2006, 14th Annual European Symposium (PDF), Lecture Notes in Computer Science, vol. 4168, pp. 684–695, doi:10.1007/11841036_61, ISBN 978-3-540-38875-3
• Broder, Andrei; Mitzenmacher, Michael (2005), "Network Applications of Bloom Filters: A Survey" (PDF), Internet Mathematics, 1 (4): 485–509, doi:10.1080/15427951.2004.10129096, S2CID 1560675
• Byers, John W.; Considine, Jeffrey; Mitzenmacher, Michael; Rost, Stanislav (2004), "Informed content delivery across adaptive overlay networks", IEEE/ACM Transactions on Networking, 12 (5): 767, CiteSeerX 10.1.1.207.1563, doi:10.1109/TNET.2004.836103, S2CID 47088273
• Calderoni, Luca; Palmieri, Paolo; Maio, Dario (2015), "Location privacy without mutual trust: The spatial Bloom filter" (PDF), Computer Communications, 68: 4–16, doi:10.1016/j.comcom.2015.06.011, hdl:10468/4762, ISSN 0140-3664
• Calderoni, Luca; Palmieri, Paolo; Maio, Dario (2018), "Probabilistic Properties of the Spatial Bloom Filters and Their Relevance to Cryptographic Protocols", IEEE Transactions on Information Forensics and Security, 13 (7): 1710–1721, doi:10.1109/TIFS.2018.2799486, hdl:10468/5767, ISSN 1556-6013, S2CID 3693354*Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew; Gruber, Robert (2006), "Bigtable: A Distributed Storage System for Structured Data", Seventh Symposium on Operating System Design and Implementation
• Charles, Denis Xavier; Chellapilla, Kumar (2008), "Bloomier filters: A second look", in Halperin, Dan; Mehlhorn, Kurt (eds.), Algorithms: ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008, Proceedings, Lecture Notes in Computer Science, vol. 5193, Springer, pp. 259–270, arXiv:0807.0928, doi:10.1007/978-3-540-87744-8_22, ISBN 978-3-540-87743-1, S2CID 643445
• Chazelle, Bernard; Kilian, Joe; Rubinfeld, Ronitt; Tal, Ayellet (2004), "The Bloomier filter: an efficient data structure for static support lookup tables", Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 30–39
• Cohen, Saar; Matias, Yossi (2003), "Spectral Bloom Filters", Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (PDF), pp. 241–252, doi:10.1145/872757.872787, ISBN 978-1581136340, S2CID 1058187
• Deng, Fan; Rafiei, Davood (2006), "Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters", Proceedings of the ACM SIGMOD Conference (PDF), pp. 25–36
• Dharmapurikar, Sarang; Song, Haoyu; Turner, Jonathan; Lockwood, John (2006), "Fast packet classification using Bloom filters", Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems (PDF), pp. 61–70, CiteSeerX 10.1.1.78.9584, doi:10.1145/1185347.1185356, ISBN 978-1595935809, S2CID 7848110, archived from the original (PDF) on 2007-02-02
• Dietzfelbinger, Martin; Pagh, Rasmus (2008), "Succinct data structures for retrieval and approximate membership", in Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.), Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Track A: Algorithms, Automata, Complexity, and Games, Lecture Notes in Computer Science, vol. 5125, Springer, pp. 385–396, arXiv:0803.3693, doi:10.1007/978-3-540-70575-8_32, ISBN 978-3-540-70574-1, S2CID 1699996
• Dillinger, Peter C.; Manolios, Panagiotis (2004a), "Fast and Accurate Bitstate Verification for SPIN", Proceedings of the 11th International Spin Workshop on Model Checking Software, Springer-Verlag, Lecture Notes in Computer Science 2989
• Dillinger, Peter C.; Manolios, Panagiotis (2004b), "Bloom Filters in Probabilistic Verification", Proceedings of the 5th International Conference on Formal Methods in Computer-Aided Design, Springer-Verlag, Lecture Notes in Computer Science 3312
• Donnet, Benoit; Baynat, Bruno; Friedman, Timur (2006), "Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives", CoNEXT 06 – 2nd Conference on Future Networking Technologies, archived from the original on 2009-05-17
• Eppstein, David; Goodrich, Michael T. (2007), "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters", Algorithms and Data Structures, 10th International Workshop, WADS 2007, Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, pp. 637–648, arXiv:0704.3313, Bibcode:2007arXiv0704.3313E
• Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Cuckoo filter: Practically better than Bloom", Proc. 10th ACM Int. Conf. Emerging Networking Experiments and Technologies (CoNEXT '14), pp. 75–88, doi:10.1145/2674005.2674994, ISBN 9781450332798. Open source implementation available on github.
• Fan, Li; Cao, Pei; Almeida, Jussara; Broder, Andrei (2000), "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" (PDF), IEEE/ACM Transactions on Networking, 8 (3): 281–293, CiteSeerX 10.1.1.41.1487, doi:10.1109/90.851975, S2CID 4779754, archived from the original (PDF) on 2017-09-22, retrieved 2018-07-30. A preliminary version appeared at SIGCOMM '98.
• Goel, Ashish; Gupta, Pankaj (2010), "Small subset queries and bloom filters using ternary associative memories, with applications" (PDF), ACM SIGMETRICS Performance Evaluation Review, 38: 143, CiteSeerX 10.1.1.296.6513, doi:10.1145/1811099.1811056
• Graf, Thomas Mueller; Lemire, Daniel (2020), "Xor Filters", ACM Journal of Experimental Algorithmics, 25: 1–16, arXiv:1912.08258, Bibcode:2019arXiv191208258M, doi:10.1145/3376122, S2CID 209405019
• Grandi, Fabio (2018), "On the analysis of Bloom filters" (PDF), Information Processing Letters, 129: 35–39, doi:10.1016/j.ipl.2017.09.004

• Kirsch, Adam; Mitzenmacher, Michael (2006), "Less Hashing, Same Performance: Building a Better Bloom Filter", in Azar, Yossi; Erlebach, Thomas (eds.), Algorithms – ESA 2006, 14th Annual European Symposium (PDF), Lecture Notes in Computer Science, vol. 4168, Springer-Verlag, Lecture Notes in Computer Science 4168, pp. 456–467, doi:10.1007/11841036, ISBN 978-3-540-38875-3, archived from the original (PDF) on 2009-01-31
• Koucheryavy, Y.; Giambene, G.; Staehle, D.; Barcelo-Arroyo, F.; Braun, T.; Siris, V. (2009), "Traffic and QoS Management in Wireless Multimedia Networks", COST 290 Final Report: 111
• Kubiatowicz, J.; Bindel, D.; Czerwinski, Y.; Geels, S.; Eaton, D.; Gummadi, R.; Rhea, S.; Weatherspoon, H.; et al. (2000), "Oceanstore: An architecture for global-scale persistent storage" (PDF), ACM SIGPLAN Notices: 190–201, archived from the original (PDF) on 2012-03-11, retrieved 2011-12-01
• Maggs, Bruce M.; Sitaraman, Ramesh K. (July 2015), "Algorithmic nuggets in content delivery" (PDF), SIGCOMM Computer Communication Review, 45 (3): 52–66, CiteSeerX 10.1.1.696.9236, doi:10.1145/2805789.2805800, S2CID 65760, archived from the original (PDF) on 2021-08-14
• Mitzenmacher, Michael; Upfal, Eli (2005), Probability and computing: Randomized algorithms and probabilistic analysis, Cambridge University Press, pp. 107–112, ISBN 9780521835404
• Mortensen, Christian Worm; Pagh, Rasmus; Pătraşcu, Mihai (2005), "On dynamic range reporting in one dimension", Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 104–111, arXiv:cs/0502032, doi:10.1145/1060590.1060606, ISBN 978-1581139600, S2CID 56473
• Mullin, James K. (1990), "Optimal semijoins for distributed database systems", IEEE Transactions on Software Engineering, 16 (5): 558–560, doi:10.1109/32.52778
• Pagh, Anna; Pagh, Rasmus; Rao, S. Srinivasa (2005), "An optimal Bloom filter replacement", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 823–829
• Palmieri, Paolo; Calderoni, Luca; Maio, Dario (2014), "Spatial Bloom Filters: Enabling Privacy in Location-Aware Applications", Proc. 10th International Conference on Information Security and Cryptology (Inscrypt 2014), vol. 8957, Springer-Verlag, Lecture Notes in Computer Science, pp. 16–36, CiteSeerX 10.1.1.471.4759, doi:10.1007/978-3-319-16745-9_2, ISBN 978-3-319-16744-2
• Porat, Ely (2009), "An optimal Bloom filter replacement based on matrix solving", in Frid, Anna E.; Morozov, Andrey; Rybalchenko, Andrey; Wagner, Klaus W. (eds.), Computer Science, Theory and Applications: Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18–23, 2009, Proceedings, Lecture Notes in Computer Science, vol. 5675, Springer, pp. 263–273, arXiv:0804.1845, doi:10.1007/978-3-642-03351-3_25, ISBN 978-3-642-03350-6, S2CID 3205108
• Pournaras, E.; Warnier, M.; Brazier, F.M.T.. (2013), "A generic and adaptive aggregation service for large-scale decentralized networks", Complex Adaptive Systems Modeling, 1:19: 19, doi:10.1186/2194-3206-1-19. Prototype implementation available on github.
• Putze, F.; Sanders, P.; Singler, J. (2007), "Cache-, Hash- and Space-Efficient Bloom Filters", in Demetrescu, Camil (ed.), Experimental Algorithms, 6th International Workshop, WEA 2007 (PDF), Lecture Notes in Computer Science, vol. 4525, Springer-Verlag, Lecture Notes in Computer Science 4525, pp. 108–121, doi:10.1007/978-3-540-72845-0, ISBN 978-3-540-72844-3
• Rottenstreich, Ori; Kanizo, Yossi; Keslassy, Isaac (2012), "The Variable-Increment Counting Bloom Filter", 31st Annual IEEE International Conference on Computer Communications, 2012, Infocom 2012 (PDF), pp. 1880–1888, CiteSeerX 10.1.1.174.7165, doi:10.1109/INFCOM.2012.6195563, ISBN 978-1-4673-0773-4
• Sethumadhavan, Simha; Desikan, Rajagopalan; Burger, Doug; Moore, Charles R.; Keckler, Stephen W. (2003), "Scalable hardware memory disambiguation for high ILP processors", 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, MICRO-36 (PDF), pp. 399–410, CiteSeerX 10.1.1.229.1254, doi:10.1109/MICRO.2003.1253244, ISBN 978-0-7695-2043-8, S2CID 195881068, archived from the original (PDF) on 2007-01-14
• Starobinski, David; Trachtenberg, Ari; Agarwal, Sachin (2003), "Efficient PDA Synchronization" (PDF), IEEE Transactions on Mobile Computing, 2 (1): 40, CiteSeerX 10.1.1.71.7833, doi:10.1109/TMC.2003.1195150
• Stern, Ulrich; Dill, David L. (1996), "A New Scheme for Memory-Efficient Probabilistic Verification", Proceedings of Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification: IFIP TC6/WG6.1 Joint International Conference, Chapman & Hall, IFIP Conference Proceedings, pp. 333–348, CiteSeerX 10.1.1.47.4101
• Swamidass, S. Joshua; Baldi, Pierre (2007), "Mathematical correction for fingerprint similarity measures to improve chemical retrieval", Journal of Chemical Information and Modeling, 47 (3): 952–964, doi:10.1021/ci600526a, PMID 17444629
• Wessels, Duane (January 2004), "10.7 Cache Digests", Squid: The Definitive Guide (1st ed.), O'Reilly Media, p. 172, ISBN 978-0-596-00162-9, Cache Digests are based on a technique first published by Pei Cao, called Summary Cache. The fundamental idea is to use a Bloom filter to represent the cache contents.
• Tarkoma, Sasu; Rothenberg, Christian Esteve; Lagerspetz, Eemil (2012), "Theory and practice of bloom filters for distributed systems", IEEE Communications Surveys & Tutorials, no. 1. (PDF), vol. 14, pp. 131–155
• Zhiwang, Cen; Jungang, Xu; Jian, Sun (2010), "A multi-layer Bloom filter for duplicated URL detection", Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010), vol. 1, pp. V1–586–V1–591, doi:10.1109/ICACTE.2010.5578947, ISBN 978-1-4244-6539-2, S2CID 3108985

बाहरी संबंध

• "Using Bloom Filters" Detailed Bloom Filter explanation using Perl
• Why Bloom filters work the way they do (Michael Nielsen, 2012)
• Bloom Filters — A Tutorial, Analysis, and Survey (Blustein & El-Maazawi, 2002) at Dalhousie University
• Table of false-positive rates for different configurations from a University of Wisconsin–Madison website
• "More Optimal Bloom Filters", Ely Porat (Nov/2007) गूगल TechTalk video on YouTube