database HyperLogLog एल्गोरिदम कैसे काम करता है?




algorithm math (3)

एक HyperLogLog एक संभाव्य डेटा संरचना है । यह सूची में विशिष्ट तत्वों की संख्या की गणना करता है। लेकिन ऐसा करने के एक सीधा तरीके की तुलना में (सेट में सेट और तत्व जोड़ना) यह लगभग अनुमानित तरीके से करता है।

यह देखने से पहले कि हाइपरलोग्लॉग एल्गोरिदम यह कैसे करता है, आपको समझना होगा कि आपको इसकी आवश्यकता क्यों है। एक सीधा तरीके से समस्या यह है कि यह अंतरिक्ष के O(distinct elements) का उपभोग करता है। केवल विशिष्ट तत्वों के बजाय यहां एक बड़ा ओ नोटेशन क्यों है? ऐसा इसलिए है क्योंकि तत्व विभिन्न आकारों के हो सकते हैं। एक तत्व 1 दूसरा तत्व हो सकता है "is this big string" । तो यदि आपके पास एक बड़ी सूची है (या तत्वों की एक विशाल धारा) तो इसमें बहुत मेमोरी होगी।

संभाव्य गणना

किसी को कई अद्वितीय तत्वों का उचित अनुमान कैसे प्राप्त हो सकता है? मान लें कि आपके पास लंबाई लंबाई की एक स्ट्रिंग है जिसमें समान संभावना के साथ {0, 1} है। संभावना है कि यह 0 शून्य से शुरू होगा, 2 शून्य के साथ, के शून्य के साथ? यह 1/2 , 1/4 और 1/2 1/2^k । इसका अर्थ यह है कि यदि आप के zeros के साथ एक स्ट्रिंग का सामना करना पड़ा है, तो आप लगभग 2^k तत्वों के माध्यम से देखा है। तो यह एक अच्छा प्रारंभिक बिंदु है। 0 और 2^k - 1 0 बीच समान रूप से वितरित तत्वों की एक सूची होने के कारण आप बाइनरी प्रतिनिधित्व में शून्य के सबसे बड़े उपसर्ग की अधिकतम संख्या को गिन सकते हैं और इससे आपको उचित अनुमान मिलेगा।

समस्या यह है कि 0 टी 2^k-1 से समान रूप से वितरित संख्याओं की धारणा प्राप्त करना बहुत मुश्किल है (हमारे द्वारा सामना किया जाने वाला डेटा अधिकतर संख्या नहीं है, लगभग कभी भी समान रूप से वितरित नहीं होता है, और किसी भी मूल्य के बीच हो सकता है। लेकिन एक अच्छा उपयोग करना हैशिंग फ़ंक्शन आप मान सकते हैं कि आउटपुट बिट्स को समान रूप से वितरित किया जाएगा और अधिकांश हैशिंग फ़ंक्शन में 0 और 2^k - 1 0 बीच आउटपुट होता है ( SHA1 आपको 0 और 2^160 बीच मान देता है)। इसलिए हमने अब तक जो हासिल किया है वह यह है कि हम आकार के log(k) बिट्स की केवल एक संख्या को स्टोर करके के बिट्स की अधिकतम कार्डिनिटी के साथ अद्वितीय तत्वों की संख्या का आकलन कर सकते हैं। नकारात्मकता यह है कि हमारे अनुमान में हमारे पास एक बड़ा अंतर है। एक अच्छी चीज जिसे हमने लगभग 1 9 84 की संभाव्य गिनती बनाई कागज (यह अनुमान के साथ थोड़ा सा चालाक है, लेकिन फिर भी हम करीब हैं)।

LogLog

आगे बढ़ने से पहले, हमें समझना होगा कि हमारा पहला अनुमान इतना अच्छा क्यों नहीं है। इसके पीछे कारण यह है कि उच्च आवृत्ति 0-उपसर्ग तत्व की एक यादृच्छिक घटना सबकुछ खराब कर सकती है। इसे सुधारने का एक तरीका है कई हैश फ़ंक्शंस का उपयोग करना, प्रत्येक हैश फ़ंक्शंस के लिए अधिकतम गणना करना और अंत में उन्हें औसत से बाहर करना। यह एक उत्कृष्ट विचार है, जो अनुमान में सुधार करेगा, लेकिन लॉगलॉग पेपर थोड़ा अलग दृष्टिकोण का उपयोग करता है (शायद क्योंकि हैशिंग महंगा है)।

उन्होंने एक हैश का इस्तेमाल किया लेकिन इसे दो भागों में बांटा। एक को बाल्टी कहा जाता है (बाल्टी की कुल संख्या 2^x ) और दूसरा - मूल रूप से हमारे हैश के समान होता है। मेरे लिए क्या चल रहा था यह प्राप्त करना मुश्किल था, इसलिए मैं एक उदाहरण दूंगा। मान लीजिए कि आपके पास दो तत्व हैं और आपके हैश फ़ंक्शन जो मान 0 से 2^10 उत्पादित 2 मान: 344 और 387 बनाते हैं। आपने 16 बाल्टी लेने का फैसला किया। मतलब आपके पास है:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

अधिक बाल्टी होने से आप भिन्नता को कम करते हैं (आप थोड़ा और अधिक जगह का उपयोग करते हैं, लेकिन यह अभी भी छोटा है)। गणित कौशल का उपयोग करके वे त्रुटि को मापने में सक्षम थे (जो 1.3/sqrt(number of buckets) )।

HyperLogLog

HyperLogLog किसी भी नए विचार पेश नहीं करता है, लेकिन पिछले अनुमान को बेहतर बनाने के लिए ज्यादातर गणित का उपयोग करता है। शोधकर्ताओं ने पाया है कि यदि आप बाल्टी से सबसे बड़ी संख्या का 30% निकालते हैं तो आप अनुमान में काफी सुधार करते हैं। उन्होंने औसत संख्याओं के लिए एक और एल्गोरिदम भी उपयोग किया। पेपर गणित-भारी है।

और मैं एक हालिया पेपर के साथ खत्म करना चाहता हूं, जो हाइपरलॉगॉग एल्गोरिदम का एक बेहतर संस्करण दिखाता है (अब तक मेरे पास पूरी तरह से समझने का समय नहीं था, लेकिन बाद में मैं इस जवाब में सुधार करूंगा)।

मैं हाल ही में अपने खाली समय में अलग-अलग एल्गोरिदम के बारे में सीख रहा हूं, और जिस पर मैं आया हूं, वह बहुत ही रोचक प्रतीत होता है जिसे हाइपरलॉगॉग एल्गोरिदम कहा जाता है - जो अनुमान लगाता है कि सूची में कितने अद्वितीय आइटम हैं।

यह मेरे लिए विशेष रूप से दिलचस्प था क्योंकि यह मुझे मेरे MySQL दिनों में वापस लाया जब मैंने देखा कि "कार्डिनालिटी" मान (जिसे मैंने हमेशा हाल ही में माना था कि इसकी अनुमानित गणना नहीं की गई थी)।

इसलिए मुझे पता है कि ( एन ) में एल्गोरिदम कैसे लिखना है जो गणना करेगा कि सरणी में कितनी अनूठी वस्तुएं हैं। मैंने इसे जावास्क्रिप्ट में लिखा था:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

लेकिन समस्या यह है कि मेरा एल्गोरिदम, जबकि ( एन ), बहुत मेमोरी ( Table में मूल्य भंडार) का उपयोग करता है।

मैं इस पेपर को ( एन ) समय में सूची में डुप्लिकेट गिनने और न्यूनतम मेमोरी का उपयोग करने के बारे में पढ़ रहा हूं।

यह बताता है कि हैशिंग और गिनती बिट्स द्वारा या किसी एक निश्चित संभावना के भीतर अनुमान लगा सकता है (सूची को समान रूप से वितरित किया जाता है) सूची में अद्वितीय वस्तुओं की संख्या।

मैंने पेपर पढ़ा है, लेकिन मुझे समझ में नहीं आता है। क्या कोई और अधिक व्यक्ति की व्याख्या दे सकता है? मुझे पता है कि हैश क्या हैं, लेकिन मुझे नहीं पता कि इन हाइपरलॉगॉग एल्गोरिदम में उनका उपयोग कैसे किया जाता है।


इस एल्गोरिदम के पीछे मुख्य चाल यह है कि यदि आप यादृच्छिक पूर्णांक की धारा देखते हैं, तो एक पूर्णांक देखें जो बाइनरी प्रतिनिधित्व कुछ ज्ञात उपसर्गों से शुरू होता है, वहां एक उच्च संभावना है कि धारा की कार्डिनालिटी 2 ^ (उपसर्ग का आकार) है ।

यही है, पूर्णांक की यादृच्छिक धारा में, ~ 50% संख्या (बाइनरी में) "1" से शुरू होती है, 25% "01" से शुरू होती है, 12,5% "001" से शुरू होती है। इसका मतलब यह है कि यदि आप एक यादृच्छिक धारा देखते हैं और "001" देखते हैं, तो इस स्ट्रीम में 8 की कार्डिनालिटी है।

(उपसर्ग "00..1" का कोई विशेष अर्थ नहीं है। यह सिर्फ इसलिए है क्योंकि अधिकांश प्रोसेसर में बाइनरी संख्या में सबसे महत्वपूर्ण बिट ढूंढना आसान है)

बेशक, यदि आप केवल एक पूर्णांक देखते हैं, तो यह मान गलत है। यही कारण है कि एल्गोरिदम स्ट्रीम को "एम" स्वतंत्र पदार्थों में विभाजित करता है और प्रत्येक प्रतिध्वनि के "00 ... 1" उपसर्ग की अधिकतम लंबाई को बनाए रखता है। फिर, प्रत्येक पदार्थ के औसत मूल्य को लेकर अंतिम मूल्य का अनुमान लगाता है।

यह इस एल्गोरिदम का मुख्य विचार है। कुछ गायब विवरण हैं (उदाहरण के लिए, कम अनुमान मूल्यों में सुधार), लेकिन यह सब कागज़ में अच्छी तरह लिखा गया है। भयानक अंग्रेजी के लिए खेद है।


अंतर्ज्ञान यह है कि यदि आपका इनपुट यादृच्छिक संख्या (जैसे शेड मान) का एक बड़ा सेट है, तो उन्हें एक सीमा पर समान रूप से वितरित करना चाहिए। आइए मान लें कि 1024 तक की मान का प्रतिनिधित्व करने के लिए सीमा 10 बिट तक है। फिर न्यूनतम मान देखा गया। आइए मान लें कि यह 10 है। फिर कार्डिनालिटी लगभग 100 (10 × 100 ≈ 1024) होने का अनुमान लगाया जाएगा।

पाठ्यक्रम के असली तर्क के लिए कागज पढ़ें।

नमूना कोड के साथ एक और अच्छी व्याख्या यहां पाई जा सकती है:
डॉन कूल एल्गोरिदम: कार्डिनालिटी अनुमान - निक का ब्लॉग





hyperloglog