मूल अवधारणा (Basic Concept)
काउंटिंग ब्लूम फिल्टर (Counting Bloom Filter) को ब्लूम फिल्टर (Bloom Filter) का एक सामान्यीकृत डेटा स्ट्रक्चर (Generalized Data Structure) के रूप में परिभाषित किया जाता है जिसे तब लागू किया जाता है जब एलिमेंट्स का एक क्रम दिया जाता है, यह जांचने के लिए कि क्या दिए गए एलिमेंट की काउंट संख्या (Count Number) दिए गए थ्रेशोल्ड (Threshold) से कम है। ब्लूम फिल्टर के सामान्यीकृत रूप के रूप में, फाल्स पॉजिटिव मैच (False Positive Matches) की संभावना है, लेकिन फाल्स नेगेटिव (False Negatives) की कोई संभावना नहीं है - दूसरे शब्दों में, एक क्वेरी या तो "संभवतः थ्रेशोल्ड से अधिक या बराबर" या "निश्चित रूप से थ्रेशोल्ड से कम" लौटाती है।
एल्गोरिदम विवरण (Algorithm Description)
- काउंटिंग ब्लूम फिल्टर के तहत उपयोग किए जाने वाले अधिकांश पैरामीटर्स, ब्लूम फिल्टर के समान ही परिभाषित हैं, जैसे n, k. m को काउंटिंग ब्लूम फिल्टर में काउंटर्स की संख्या के रूप में दर्शाया जाता है, जो ब्लूम फिल्टर में m बिट्स का विस्तार है।
- एक खाली काउंटिंग ब्लूम फिल्टर को m काउंटर्स के रूप में सेट किया जाता है, सभी 0 पर आरंभ किए गए।
- ब्लूम फिल्टर के समान, k विभिन्न हैश फंक्शन्स भी परिभाषित होने चाहिए, जिनमें से प्रत्येक किसी सेट एलिमेंट को m काउंटर एरे पोजीशन में से एक पर मैप या हैश करने के लिए जिम्मेदार है, जिससे एक समान रैंडम वितरण (Uniform Random Distribution) बनता है। यह भी समान है कि k एक कॉन्स्टेंट है, m से बहुत कम, जो जोड़े जाने वाले एलिमेंट्स की संख्या के आनुपातिक (Proportional) है।
- ब्लूम फिल्टर का मुख्य सामान्यीकरण एलिमेंट जोड़ना है। एक एलिमेंट जोड़ने के लिए, इसे k हैश फंक्शन्स में से प्रत्येक में डालकर k एरे पोजीशन प्राप्त करें और इन सभी पोजीशन पर काउंटर्स को 1 बढ़ाएं।
- थ्रेशोल्ड θ के साथ एक एलिमेंट के लिए क्वेरी करने के लिए (सत्यापित करें कि एलिमेंट की काउंट संख्या θ से कम है या नहीं), इसे k हैश फंक्शन्स में से प्रत्येक में डालकर k काउंटर पोजीशन प्राप्त करें।
- यदि इन पोजीशन पर किसी भी काउंटर का मान θ से छोटा है, तो एलिमेंट की काउंट संख्या निश्चित रूप से θ से कम है − यदि यह अधिक या बराबर होती, तो सभी संबंधित काउंटर अधिक या θ के बराबर होते।
- यदि सभी θ से अधिक या बराबर हैं, तो या तो काउंट वास्तव में θ से अधिक या बराबर है, या काउंटर्स संयोग से θ से अधिक या बराबर हो गए हैं।
- यदि सभी θ से अधिक या बराबर हैं भले ही काउंट θ से कम हो, इस स्थिति को फाल्स पॉजिटिव (False Positive) के रूप में परिभाषित किया जाता है। ब्लूम फिल्टर की तरह, इसे भी कम से कम किया जाना चाहिए।
