Approximate Membership Query Filter
अनुमानित सदस्यता प्रश्न फ़िल्टर (ए. एम. क्यू.-फ़िल्टर) स्थान-कुशल संभावित डेटा संरचनाओं का एक समूह है जो अनुमानित सदस्यता प्रश्नों का समर्थन करता है। एक अनुमानित सदस्यता प्रश्न का उत्तर है कि क्या कोई तत्व एक समूह में है या नहीं, जिसकी गलत सकारात्मक दर है। ब्लूम फ़िल्टर सबसे अधिक ज्ञात ए. एम. क्यू.-फ़िल्टर हैं, लेकिन अन्य ए. एम. क्यू.-फ़िल्टर हैं जो अतिरिक्त संचालन का समर्थन करते हैं या जिनकी अलग-अलग स्थान आवश्यकताएँ होती हैं। ए. एम. क्यू.-फिल्टर के कई अनुप्रयोग हैं, मुख्य रूप से वितरित प्रणालियों और डेटाबेस में। वहाँ, उनका उपयोग अक्सर नेटवर्क अनुरोध या आई/ओ संचालन से बचने के लिए किया जाता है जो उन तत्वों का अनुरोध करने के परिणामस्वरूप होता है जो मौजूद नहीं हैं। अनुमानित सदस्यता प्रश्न समस्या अनुमानित सदस्यता प्रश्न समस्या तत्वों के एक समूह के बारे में जानकारी को स्थान-कुशल तरीके से संग्रहीत करना है। लक्ष्य इस प्रश्न का उत्तर देना है कि क्या कोई तत्व सेट में है या नहीं, जबकि अधिकतम संभावना के साथ गलत सकारात्मक की अनुमति देता है। सभी ए. एम. क्यू.-फिल्टर इस ऑपरेशन लुकअप का समर्थन करते हैं। गतिशील ए. एम. क्यू.-फिल्टर किसी भी समय सम्मिलन की अनुमति देते हैं जबकि स्थिर ए. एम. क्यू.-फिल्टर को अतिरिक्त तत्व डालने के बाद फिर से बनाया जाता है। कुछ ए. एम. क्यू.-फ़िल्टर तत्वों को हटाने या दो फ़िल्टरों को मिलाने जैसे अतिरिक्त कार्यों का समर्थन करते हैं। एक खोज यह निर्धारित कर सकती है कि क्या कोई तत्व निश्चित रूप से सेट में नहीं है या क्या कोई तत्व संभवतः सेट में हैः हमेशा सही लौटता है। : की संभावना के साथ गलत लौटें। एक गलत सकारात्मक एक तत्व की खोज है जो सेट का हिस्सा नहीं है, लेकिन खोज वैसे भी सही लौटती है। ऐसा होने की संभावना गलत सकारात्मक दर है। ए. एम. क्यू.-फिल्टर के लिए गलत नकारात्मक (खोज गलत बताती है हालांकि तत्व सेट का हिस्सा है) की अनुमति नहीं है। प्रविष्टि एक तत्व डालने के बाद इस तत्व के लिए खोज सही होनी चाहिए। गतिशील ए. एम. क्यू.-फिल्टर डेटा संरचना के पुनर्निर्माण के बिना एक बार में एक तत्व डालने का समर्थन करते हैं। अन्य ए. एम. क्यू.-फ़िल्टरों को प्रत्येक प्रविष्टि के बाद फिर से बनाया जाना है। इन्हें स्थिर ए. एम. क्यू.-फिल्टर कहा जाता है। गलत सकारात्मक दर बनाम स्थान भंडारण आकार और गलत सकारात्मक दर के बीच एक समझौता होता है। भंडारण स्थान बढ़ाने से गलत सकारात्मक दर कम हो जाती है। सैद्धांतिक निचली सीमा प्रत्येक तत्व के लिए बिट होती है। गतिशील ए. एम. क्यू.-फ़िल्टर इस निचली सीमा तक नहीं पहुँच सकते हैं। उन्हें डालने के लिए कम से कम टुकड़ों की आवश्यकता होती है। अलग-अलग ए. एम. क्यू.-फ़िल्टर में गलत सकारात्मक दरों और स्थान आवश्यकताओं की अलग-अलग श्रेणियाँ होती हैं। सबसे अच्छा ए. एम. क्यू.-फ़िल्टर चुनना अनुप्रयोग पर निर्भर करता है। डेटा संरचनाएँ अनुमानित सदस्यता प्रश्न समस्या को हल करने के विभिन्न तरीके हैं। सबसे अधिक ज्ञात डेटा संरचना ब्लूम फिल्टर हैं, लेकिन अन्य डेटा संरचनाएं हैं जो कुछ गलत सकारात्मक दरों और स्थान आवश्यकताओं के लिए बेहतर प्रदर्शन करती हैं, अतिरिक्त संचालन का समर्थन करती हैं, या अन्य सम्मिलन और खोज समय होती हैं। कुछ प्रसिद्ध ए. एम. क्यू.-फ़िल्टर हैंः ब्लूम फ़िल्टर एक ब्लूम फ़िल्टर हैश कार्यों के साथ बिट्स की एक छोटी श्रृंखला है। प्रत्येक हैश फ़ंक्शन सरणी में स्थितियों में से एक के लिए एक तत्व को मैप करता है। शुरुआत में, सरणी के सभी बिट्स को शून्य पर सेट किया जाता है। एक तत्व डालने के लिए, सभी हैश कार्यों की गणना की जाती है और सरणी में सभी संबंधित बिट्स को एक पर सेट किया जाता है। किसी तत्व को देखने के लिए, सभी हैश कार्यों की गणना की जाती है। यदि सभी संबंधित बिट्स सेट किए जाते हैं, तो सही लौटाया जाता है। गलत सकारात्मक दर को कम करने के लिए, हैश कार्यों की संख्या को बढ़ाया जा सकता है। कोशेंट फ़िल्टर कोशेंट फ़िल्टर का विचार एक तत्व को हैश करना और उसके फिंगरप्रिंट को कम से कम महत्वपूर्ण बिट्स में विभाजित करना है जिसे शेष और सबसे महत्वपूर्ण बिट्स को कोशेंट कहा जाता है। भागफल यह निर्धारित करता है कि हैश तालिका में शेष कहाँ संग्रहीत किया जाता है। हैश टेबल में प्रत्येक स्लॉट के लिए अतिरिक्त तीन बिट्स का उपयोग नरम टकराव (समान भागफल लेकिन अलग-अलग अवशेष) को हल करने के लिए किया जाता है। क्वोशन्ट फिल्टर्स द्वारा उपयोग की जाने वाली जगह की तुलना ब्लूम फिल्टर्स से की जा सकती है, लेकिन क्वोशन्ट फिल्टर्स को उनकी गलत सकारात्मक दर को प्रभावित किए बिना विलय किया जा सकता है। कोयल फ़िल्टर कोयल हैशिंग पर आधारित होते हैं, लेकिन केवल तत्वों के उंगलियों के निशान हैश टेबल में संग्रहीत किए जाते हैं। प्रत्येक तत्व के दो संभावित स्थान हैं। दूसरे स्थान की गणना पहले स्थान और तत्व के फिंगरप्रिंट के आधार पर की जाती है। यदि किसी तत्व के लिए दोनों संभावित स्थान भरे हुए हैं तो पहले से ही डाले गए तत्वों को स्थानांतरित करने के लिए यह आवश्यक है। भार सीमा तक पहुँचने के बाद कोयल फिल्टर डालने की गति कम हो जाती है। यह संभव है कि एक सम्मिलन विफल हो जाए, और टेबल को फिर से बनाया जाना चाहिए। जबकि ब्लूम फिल्टर में हमेशा निरंतर सम्मिलन समय होता है, लेकिन जैसे-जैसे भार कारक बढ़ता है गलत सकारात्मक दर भी बढ़ जाती है। एक कोयल फिल्टर तत्वों को हटाने का समर्थन करता है यदि हम निश्चित रूप से जानते हैं कि तत्व डाला गया था। यह ब्लूम फिल्टर और कोशेंट फिल्टर पर एक लाभ है जो इस ऑपरेशन का समर्थन नहीं करते हैं। ज़ोर फ़िल्टर स्थिर ए. एम. क्यू.-फ़िल्टर होते हैं जो एक ब्लूमियर फ़िल्टर पर आधारित होते हैं और विचार पूर्ण हैश टेबल का उपयोग करते हैं। कोयल फिल्टर के समान वे हैश टेबल में तत्वों के उंगलियों के निशान को बचाते हैं। विचार यह है कि किसी तत्व के लिए एक क्वेरी सही है यदि दिए गए तीन हैश कार्यों का xor का फिंगरप्रिंट है। हैश टेबल का निर्माण करते समय, प्रत्येक तत्व को इसके तीन स्लॉट में से एक इस तरह से सौंपा जाता है कि इस स्लॉट को कोई अन्य तत्व नहीं सौंपा जाता है। सभी तत्वों को असाइन करने के बाद, हम प्रत्येक तत्व के लिए उसके स्लॉट का मूल्य तत्व के दो अन्य (असाइन नहीं किए गए) स्लॉट और तत्व के फिंगरप्रिंट के xor पर सेट करते हैं। यह निर्माण एल्गोरिथ्म विफल हो सकता है और हैश टेबल के पुनर्निर्माण के बिना कोई गतिशील सम्मिलन संभव नहीं है। इस हैश टेबल का निर्माण केवल बिट्स प्रति तत्व का उपयोग करके किया जा सकता है। इस फिल्टर का नुकसान यह है कि यदि अतिरिक्त तत्वों को जोड़ा जाता है तो डेटा संरचना को फिर से बनाना पड़ता है। इनका उपयोग उन अनुप्रयोगों में किया जाता है जहाँ बाद में किसी भी तत्व को जोड़ना नहीं पड़ता है और स्थान महत्वपूर्ण है। ए. एम. क्यू.-फ़िल्टरों के विशिष्ट अनुप्रयोग वितरित प्रणालियाँ और डाटाबेस प्रणालियाँ हैं। ए. एम. क्यू.-फ़िल्टर डेटाबेस या रिमोट मेमोरी की कुंजी के सेट के लिए एक प्रॉक्सी के रूप में कार्य करता है। डेटाबेस या रिमोट मेमोरी के लिए एक अनुमानित धीमी क्वेरी के प्रदर्शन से पहले ए. एम. क्यू.-फिल्टर का उपयोग यह अनुमान लगाने के लिए किया जाता है कि क्या कुंजी डेटाबेस या रिमोट मेमोरी में है। धीमी क्वेरी केवल तभी की जाती है जब ए. एम. क्यू.-फ़िल्टर सही आता है। केवल एक गलत सकारात्मक परिणाम एक अनावश्यक आई/ओ ऑपरेशन या दूरस्थ पहुंच की ओर ले जाता है। अनुप्रयोग कई हैं और इसमें पैकेज और संसाधन रूटिंग, पी2पी नेटवर्क और वितरित कैशिंग शामिल हैंः एएमक्यू-फिल्टर का उपयोग अक्सर महंगे डिस्क एक्सेस से बचने के लिए इन-मेमोरी डेटा संरचना के रूप में किया जाता है। एक अनुप्रयोग लॉग-संरचित विलय-वृक्ष या एल. एस. एम.-वृक्ष है। उनके पास एक तेज़ इन-मेमोरी घटक होता है और एक डिस्क पर एक या कई घटक होते हैं जो स्वयं पेड़ होते हैं। इन-मेमोरी घटक को डिस्क घटकों के साथ विलय करने की तुलना में इन-मेमोरी घटक में तत्वों को तब तक डाला जाता है जब तक कि यह अपने अधिकतम आकार तक नहीं पहुंच जाता। खोज में तेजी लाने के लिए कई एल. एस. एम.-ट्री ए. एम. क्यू.-फिल्टर जैसे ब्लूम फिल्टर या कोशंट फिल्टर को लागू करते हैं। वे फ़िल्टर प्रत्येक घटक के लिए अनुमानित हैं कि इसमें कौन से तत्व संग्रहीत हैं। एलएसएम-ट्रीज का उपयोग अपाचे एस्टेरिक्सडीबी, बिगटेबल, एचबेस, लेवलडीबी, एसक्यूलाइट4 जैसे डेटाबेस में किया जाता है। नेटवर्क ए. एम. क्यू.-फिल्टर के लिए बहुत सारे अनुप्रयोग प्रदान करते हैं। इनका उपयोग एक अलग सर्वर पर स्थित डेटा के एक समूह का अनुमान लगाने के लिए किया जाता है। कई मामलों में उन ए. एम. क्यू.-फिल्टरों को अपरिवर्तनीय के रूप में देखा जा सकता है। भले ही रिमोट सर्वर पर सेट बदल जाता है, ए. एम. क्यू.-फ़िल्टर को अक्सर तुरंत अपडेट नहीं किया जाता है, लेकिन कुछ गलत सकारात्मक को सहन किया जाता है। इस अनुप्रयोग का एक उदाहरण वेब कैश साझाकरण है। यदि किसी प्रॉक्सी के पास कैश मिस है तो वह यह निर्धारित करना चाहता है कि क्या किसी अन्य प्रॉक्सी के पास अनुरोधित डेटा है। इसलिए, प्रॉक्सी को पता होना चाहिए या कम से कम अनुमानित होना चाहिए कि क्या किसी अन्य प्रॉक्सी के पास अनुरोधित वेब पेज है। इसे समय-समय पर यू. आर. एल. सूचियों को प्रसारित करने के बजाय वेब पृष्ठों के यू. आर. एल. के स्थिर ए. एम. क्यू.-फ़िल्टर को प्रसारित करके संग्रहीत किया जा सकता है। इस सेटिंग में, गलत नकारात्मक हो सकते हैं यदि आवधिक अद्यतनों के बीच कैश बदल जाता है। यही अवधारणा पी2पी नेटवर्क पर भी लागू की जा सकती है। ए. एम. क्यू.-फ़िल्टर का उपयोग नेटवर्क के प्रत्येक नोड पर क्या संग्रहीत है, इसका अनुमान लगाने के लिए किया जा सकता है। फ़िल्टर को नोड्स के वास्तविक दस्तावेजों के आईडी या मुख्य शब्दों से भरा जा सकता है। गलत सकारात्मक केवल कुछ अनावश्यक अनुरोधों की ओर ले जाते हैं। ए. एम. क्यू.-फिल्टर के पी. 2. पी. नेटवर्क में और अनुप्रयोग हैं, उदाहरण के लिए विभिन्न नोड्स पर संग्रहीत सेटों के बीच अंतर या प्रतिच्छेदन का पता लगाना। संदर्भ संभावित डेटा संरचनाएँ