/ / ब्लूम फिल्टर या कोयल हैशिंग? - एल्गोरिदम, हैश, फ़िल्टर

ब्लूम फिल्टर या कोयल हैशिंग? - एल्गोरिदम, हैश, फ़िल्टर

आप कौन सा पसंद करते हैं और क्यों?

दोनों का उपयोग समान कार्यों को पूरा करने के लिए किया जा सकता है लेकिन मैं यह देखने के लिए उत्सुक हूं कि लोगों ने वास्तविक अनुप्रयोगों में क्या उपयोग किया है और ऐसा करने के उनके तर्क।

उत्तर:

जवाब के लिए 9 № 1

ब्लूम फिल्टर और कोयल फिल्टर समान परिस्थितियों में उपयोग किए जाते हैं लेकिन वहां बहुत सारे मतभेद हैं जो आम तौर पर निर्धारित करते हैं कि कौन सी बेहतर विकल्प है।

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

आज के सास मॉडल के साथ एक और आम उदाहरणएक मूल्य-प्रति-कॉल के साथ एक दूरस्थ आरईएसटी सेवा होगी। बाइनरी उत्तर के साथ कोई एपीआई कॉल जैसे "यह पता INVALID" 9 0% डुप्लिकेट क्वेरी को खत्म करने के लिए ब्लूम फ़िल्टर का उपयोग कर सकता है! ध्यान दें कि चूंकि ब्लूम और कोयल फिल्टर में झूठी सकारात्मक हैं, इसलिए वे व्यस्त संचालन के लिए उपयोगी नहीं हैं "क्या यह पता वैध है"

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

कोयल / ब्लूम के बीच उल्लेखनीय मतभेदों में शामिल हैं:

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

  • झूठी सकारात्मक दर। कोयल फिल्टर अधिक अंतरिक्ष कुशल हैं। दोनों संरचनाओं के लिए कई उपयोग मामलों निम्न स्तर नेटवर्किंग पर केंद्रित हैं। कमजोर हार्डवेयर पर एक ही झूठी सकारात्मक दर के लिए ~ 40% उच्च गुणवत्ता वाले कोयल फ़िल्टर की उच्च दक्षता महत्वपूर्ण हो सकती है। सी ++ में संदर्भ कार्यान्वयन, अतिरिक्त बाल्टी प्रिंटिंग के लिए प्रत्येक बाल्टी के भीतर वस्तुओं को प्रकार देता है, छोटे फिंगरप्रिंटों को स्टोर करने के लिए एक बाल्टी के भीतर किसी आइटम की स्थिति का लाभ लेता है। अतिरिक्त पुस्तकालयों में मैं बाद में उल्लेख करूँगा (मेरा सहित) डॉन " ऐसा करो। अगर कोई मेरी लाइब्रेरी का उपयोग करता है तो मैं इसे जोड़ सकता हूं :)।

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

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

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

  • समर्थन। कोकू फिल्टर कई भाषाओं के लिए नए और स्थिर पुस्तकालय हैं जो वास्तव में मौजूद नहीं हैं।

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

निर्बाध प्लग: मैं जावा के लिए एक कोयल फ़िल्टर लाइब्रेरी के डेवलपर हूं। CuckooFilter4J । इसमें बाल्टी अर्द्ध-प्रकार का उपयोग किया जा रहा हैपेपर ताकि स्पेस दक्षता संदर्भ कार्यान्वयन से कुछ हद तक कम हो। प्रोजेक्ट रीडेमे में मेरे पास अन्य कार्यान्वयन के लिंक हैं जिन्हें मैं जानता हूं। कौन सी संरचना बेहतर है आपके उपयोग के मामले पर निर्भर करती है, लेकिन अधिकतर यह है कि आपकी भाषा के लिए एक ठोस कोयल फ़िल्टर कार्यान्वयन मौजूद है या नहीं।

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

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


जवाब के लिए 8 № 2

शराब या पनीर आप कौन सा पसंद करते हैं?

ब्लूम फ़िल्टर जब आपके पास है सिमित जगह, उच्च पूछताछ लागत, तथा ज्यादातर नकारात्मक प्रश्न.
उस मामले में, ए ब्लूम फ़िल्टर साथ में प्रति बिट 8 बिट्स तथा 4 हैश फ़ंक्शन आपको देता है 2.5% झूठी सकारात्मक दर; आप लगभग प्रश्नों को संसाधित करते हैं 40 गुना तेजी से पहले की तुलना में, की लागत पर प्रति बाइट 1 बाइट.

दूसरी ओर, अगर इनमें से कोई भी पिछली स्थितियां नहीं पकड़ती हैं, ए हैश टेबल कैश के रूप में काम कर रहा है समझ में आता है, हालांकि यह स्पष्ट रूप से एक ले जाएगा प्रति प्रवेश एक से अधिक बाइट :-)

आप भी कठिन किनारे के मामलों को छोड़ सकते हैं कोयल हैशिंग अगर यह एक कैश है। इससे आकार में वृद्धि की समस्या भी बढ़ जाती है कोयल हैश टेबल (या रैखिक हैश के अलावा कुछ भी) moot।


जवाब के लिए 5 № 3

कोयल फ़िल्टर।

"कोयल फ़िल्टर: ब्लूम से व्यावहारिक रूप से बेहतर।" बिन फैन, डेविड एंडर्सन, माइकल कामिंस्की, माइकल मिट्टनमेकर CoNext 2014। http://dx.doi.org/10.1145/2674005.2674994

लेखकों में से एक से " ब्लॉग:

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


जवाब के लिए 2 № 4

मैं कोयल हैशिंग पसंद करते हैं। मैं झूठी सकारात्मक चीजों से सावधान हूं जो उच्च भरने वाले कारकों पर खिलने वाले फ़िल्टर के साथ दिखाई दे सकते हैं।
एक आवेदन में कोयल हैशिंग का इस्तेमाल किया है जहां हमारे पास बहुत बड़ी हैश टेबल थीं और मेमोरी प्रेशर के मुद्दों में चल रही थीं। कृपया मेरी eCollections लाइब्रेरी को देखें http://codeplex.com/ecollections कोयल हैशिंग के एक प्रकार के कार्यान्वयन के लिए।

सधन्यवाद,


जवाब के लिए 0 № 5

यदि मैं झूठी सकारात्मक सहन कर सकता हूं और स्थान महत्वपूर्ण है, तो मैं ब्लूम फ़िल्टर का उपयोग करता हूं क्योंकि इसमें कम जगह होती है। अन्यथा, मैं एक हैश का उपयोग करता हूं।