ब्लूम फ़िल्टर की अनुमानित आबादी की गणना

Question

आकार एन-बिट्स और के हैश फ़ंक्शन के ब्लूम फ़िल्टर को देखते हुए, जिनमें से एम-बिट्स (जहां एम < = N) फ़िल्टर सेट हैं।

क्या ब्लूम फ़िल्टर में डाले गए तत्वों की संख्या का अनुमान लगाना संभव है?

सरल उदाहरण

मैं निम्न उदाहरण पर विचार कर रही किया गया है, 100-बिट और 5 हैश फंक्शन जहां 10-बिट सेट कर रहे हैं की एक बीएफ संभालने ...

बेस्ट स्थिति: हैश फ़ंक्शन मानते हैं कि वास्तव में कुछ एक्स संख्याओं के लिए कुछ सही और विशिष्ट रूप से मानचित्र हैं, फिर 10-बिट्स सेट किए गए हैं, हम कह सकते हैं कि बीएफ

सबसे खराब स्थिति परिदृश्य में केवल 2 तत्व डाले गए हैं: मानना हैश फ़ंक्शन खराब हैं और लगातार एक ही बिट पर मानचित्र हैं (अभी तक एक दूसरे के बीच अद्वितीय), तो हम कह सकते हैं कि 10 तत्व बीएफ

यह रेंज [2,10] लगता है जहां इस श्रेणी में abouts शायद फ़िल्टर की झूठी-सकारात्मक संभावना द्वारा निर्धारित किया गया है I मैं इस बिंदु पर फंस गया हूँ।

Answer 1

यह प्रश्न मुझे थोड़ा चिंतित करता है क्योंकि better algorithms लगभग कम मात्रा में भंडारण के साथ विशिष्ट तत्वों की संख्या की गणना करने के लिए हैं।

फिर भी, अगर हमें ब्लूम फ़िल्टर का उपयोग करना चाहिए, तो मान लीजिए कि हैश फ़ंक्शन यादृच्छिक ऑर्केल्स हैं (सभी मान स्वतंत्र रूप से चुने गए हैं, या "वास्तव में सही" हैं, सही हैशिंग के साथ उलझन में नहीं हैं)। अब हमारे पास गेंदें और डिब्बे की समस्या है: MN डिब्बे में गेंदें हैं, हमने कितनी गेंदें फेंक दीं? चलो B फेंकने वाली गेंदों की संख्या हो; आइटम की संख्या B/K है, क्योंकि प्रत्येक आइटम के लिए हम K गेंदों को फेंक देते हैं।

गेंदों और डिब्बे प्रक्रियाओं के लिए मानक अनुमान प्रत्येक बिन को एक स्वतंत्र पोइसन प्रक्रिया के रूप में मॉडल करना है; एक बिन पर कब्जा करने से पहले समय तेजी से वितरित किया जाता है। 1 को सभी गेंदों को फेंकने के लिए समय लगता है, इस घातीय वितरण की दर से λ अनुमानित अधिकतम संभावना Pr(Exponential[λ] < 1) = M/N, 1 - exp(-λ) = M/N और λ = -log(1 - M/N) को संतुष्ट करती है। पैरामीटर λ गेंदों की संख्या के समान है, इसलिए वस्तुओं की संख्या के लिए अनुमान B ≈ -N log(1 - M/N)/K है।

संपादित करें: N डिब्बे हैं, इसलिए हमें N से गुणा करने की आवश्यकता है।

Answer 2

Wikipedia पर प्रविष्टि आपको किसी विशेष बिट सेट की संभावना के लिए एक सूत्र प्रदान करती है, यह मानते हुए कि हैश फ़ंक्शन सब कुछ यादृच्छिक बनाते हैं। यह 1 - (1-1/m)^kn है। चूंकि फ़िल्टर में m बिट्स हैं, इसका मतलब है कि बिट्स सेट की अपेक्षित/औसत संख्या m(1-(1-1/m)^kn) होगी। तो n चुनकर n के लिए आप एक उचित अनुमानित अनुमान के साथ आ सकते हैं जो वास्तव में निर्धारित बिट्स की संख्या के बराबर बनाता है।

इस तरह के अनुमान को कितना सटीक होने की संभावना है और यह जानने के लिए, बिट्स सेट की संख्या के भिन्नता का विचार होना अच्छा लगेगा। आप इसे ठीक से काम कर सकते हैं, लेकिन यह गर्दन में दर्द का कुछ है। आप इस तथ्य का उपयोग कर सकते हैं कि Var(X) = E(X^2) - E(X)^2।इस मामले में, E(X^2) अधिकतर संभावनाओं पर निर्भर करता है कि बिट्स के जोड़े दोनों सेट किए जाएंगे, और आप "बिट 0 सेट और बिट 1 जैसे विवरणों की संभावना पर विचार करके इसे बाहर कर सकते हैं और अन्य सभी बिट स्पष्ट हैं" और "बिट 0 स्पष्ट है" और "0 और 1 को छोड़कर सभी बिट्स स्पष्ट हैं"।