मूल अवधारणा
एक काउंटिंग ब्लूम फ़िल्टर को ब्लूम फ़िल्टर की एक सामान्यीकृत डेटा संरचना के रूप में परिभाषित किया जाता है जिसे यह परीक्षण करने के लिए कार्यान्वित किया जाता है कि तत्वों का एक क्रम दिए जाने पर किसी दिए गए तत्व की गणना संख्या दी गई सीमा से कम है या नहीं। एक सामान्यीकृत रूप के रूप में, ब्लूम फ़िल्टर के झूठे सकारात्मक मिलान की संभावना है, लेकिन झूठे नकारात्मक की कोई संभावना नहीं है - दूसरे शब्दों में, एक क्वेरी या तो "संभवतः सीमा से अधिक या बराबर" या "निश्चित रूप से सीमा से कम" लौटाती है।
एल्गोरिदम विवरण
- ब्लूम फ़िल्टर की गिनती के तहत उपयोग किए जाने वाले अधिकांश पैरामीटर, ब्लूम फ़िल्टर के साथ समान परिभाषित किए जाते हैं, जैसे n, k। m को काउंटिंग ब्लूम फ़िल्टर में काउंटरों की संख्या के रूप में दर्शाया जाता है, जो ब्लूम फ़िल्टर में m बिट्स का विस्तार है।
- एक खाली काउंटिंग ब्लूम फ़िल्टर को एम काउंटर के रूप में सेट किया गया है, सभी को 0 से प्रारंभ किया गया है।
- ब्लूम फ़िल्टर के समान, k विभिन्न हैश फ़ंक्शन भी परिभाषित होने चाहिए, जिनमें से प्रत्येक एक समान यादृच्छिक वितरण बनाने के लिए m काउंटर सरणी पदों में से किसी एक के लिए कुछ सेट तत्व को मैप या हैश करने के लिए जिम्मेदार है। यह भी समान है कि k एक स्थिरांक है, जो m से बहुत कम है, जो कि जोड़े जाने वाले तत्वों की संख्या के समानुपाती होता है।
- ब्लूम फ़िल्टर का मुख्य सामान्यीकरण एक तत्व को जोड़ना है। किसी तत्व को जोड़ने के लिए, k सरणी स्थिति प्राप्त करने के लिए इसे प्रत्येक k हैश फ़ंक्शन में डालें और इन सभी पदों पर काउंटर 1 को बढ़ाएं।
- थ्रेशोल्ड वाले तत्व के लिए क्वेरी करने के लिए (सत्यापित करें कि क्या तत्व की गिनती संख्या θ से कम है), k काउंटर स्थिति प्राप्त करने के लिए इसे प्रत्येक k हैश फ़ंक्शन में डालें।
- यदि इन पदों पर कोई भी काउंटर θ से छोटा है, तो तत्व की गिनती संख्या निश्चित रूप से θ से छोटी है - यदि यह अधिक और बराबर होती, तो सभी संबंधित काउंटर से अधिक या बराबर होते। ली>
- यदि सभी के उच्च या बराबर हैं, तो या तो गिनती वास्तव में अधिक है या θ के बराबर है, या काउंटर संयोग से θ के उच्च या बराबर हैं।
- यदि सभी से अधिक या बराबर हैं, भले ही गिनती से कम है, इस स्थिति को झूठी सकारात्मक के रूप में परिभाषित किया गया है। ब्लूम फ़िल्टर की तरह, इसे भी छोटा किया जाना चाहिए।