अनुमानित गणना एल्गोरिथ्म

अनुमानित गणना एल्गोरिथ्म व्यापक मात्रा में स्मृति का उपयोग करके बड़ी संख्या में घटनाओं की गणना का विवरण देता है। 1977 में बेल लैब्स के रॉबर्ट मॉरिस (प्रसंभाव्यतावादी) द्वारा आविष्कार किया गया, यह काउंटर (डिजिटल) के लिए यादृच्छिक एल्गोरिदम का उपयोग किया जाता है। है। 1980 के दशक की शुरुआत में INRIA रोक्वेनकोर्ट के फिलिप फ्लेजोलेट द्वारा इसका पूरी तरह से विश्लेषण किया गया था, जिन्होंने अनुमानित गणना नाम गढ़ा था, और अनुसंधान समुदाय के मध्य इसकी मान्यता में दृढ़ता से योगदान दिया था। जब अनुमान की उच्च गुणवत्ता और विफलता की कम संभावना पर ध्यान केंद्रित किया गया, तो स्पष्टीकरण नेल्सन और यू ने दिखाया कि मॉरिस काउंटर में बहुत ही मामूली संशोधन समस्या के लिए सभी एल्गोरिदम के मध्य स्पर्शोन्मुख रूप से इष्टतम है।^[1] एल्गोरिदम को स्ट्रीमिंग एल्गोरिदम के अग्रदूतों में से एक माना जाता है, और डेटा स्ट्रीम की आवृत्ति क्षणों को निर्धारित करने की अधिक सामान्य समस्या इस क्षेत्र में केंद्रीय रही है।

संचालन का सिद्धांत

मॉरिस के एल्गोरिदम का उपयोग करते हुए, काउंटर वास्तविक गणना के परिमाण अनुमान के क्रम का प्रतिनिधित्व करता है। सन्निकटन गणितीय रूप से निष्पक्ष अनुमानक है।

काउंटर को बढ़ाने के लिए, एक छद्म-यादृच्छिक घटना का उपयोग किया जाता है, जैसे कि वृद्धि एक संभाव्य घटना है। समिष्ट बचाने के लिए केवल घातांक को ही रखा जाता है। उदाहरण के लिए, आधार 2 में, काउंटर 1, 2, 4, 8, 16, 32 और दो की सभी घातों की गणना का अनुमान लगा सकता है। स्मृति की आवश्यकता केवल घातांक को पकड़ने की है।

उदाहरण के तौर पर, 4 से 8 तक बढ़ाने के लिए, छद्म-यादृच्छिक संख्या उत्पन्न की जाएगी जिससे कि काउंटर बढ़ने की संभावना 0.25 हो। नहीं तो काउंटर 4 पर ही रहता है.

नीचे दी गई तालिका काउंटर के कुछ संभावित मूल्यों को दर्शाती है:

काउंटर का संग्रहीत बाइनरी मान	सन्निकटन	वास्तविक गणना के लिए संभावित मानों की सीमा	अपेक्षा (पर्याप्त रूप से बड़ी एन, समान वितरण)
0	1	0, or initial value	0
1	2	1 or more	2
10	4	2 or more	6
11	8	3 or more	14
100	16	4 or more	30
101	32	5 or more	62

यदि काउंटर में 101 का मान है, जो 5 के घातांक (101 के दशमलव समतुल्य) के समकक्ष है, तो अनुमानित गणना है $2^{5}$ , या 32. इसकी काफी कम संभावना है कि वृद्धि की घटनाओं की वास्तविक गणना 5 थी ( ${\frac {1}{1024}}=1\times {\frac {1}{2}}\times {\frac {1}{4}}\times {\frac {1}{8}}\times {\frac {1}{16}}$ ). वृद्धि की घटनाओं की वास्तविक संख्या प्राय: 32 होने की संभावना है, लेकिन यह स्वेच्छन्दता से अधिक हो सकती है (39 से ऊपर की वास्तविक गणनाओं के लिए घटती संभावनाओं के साथ)।

काउंटर मानों का चयन

जबकि काउंटर मानों के रूप में 2 की शक्तियों का उपयोग करना मेमोरी दक्ष है, यादृच्छिक मान्यता एक क्रियाशील त्रुटि श्रेणी बनाते हैं, और लघु मानों में बड़े मानों की तुलना में अधिक त्रुटि अनुपात होगा। काउंटर मानों का चयन करने की अन्य विधियाँ मानों का इष्टतम समकक्ष प्रदान करने के लिए मेमोरी उपलब्धता, वांछित त्रुटि अनुपात, या गणना सीमा जैसे मापदंडों पर विचार करती हैं।^[2]

चूंकि, जब कई काउंटर समान मान साझा करते हैं, तो मान सबसे बड़ी गणना सीमा वाले काउंटर के अनुसार अनुकूलित होते हैं, और लघु काउंटरों के लिए उप-इष्टतम सटीकता उत्पन्न करते हैं। स्वतंत्र काउंटर अनुमान बकेट बनाए रखने से शमन प्राप्त किया जाता है,^[3] जो बड़े काउंटर के प्रभाव को बाल्टी के अन्य काउंटरों तक सीमित कर देता है।

एल्गोरिदम

एल्गोरिदम को हाथ से कार्यान्वित किया जा सकता है। काउंटर को बढ़ाते समय, एक सिक्के को काउंटर के वर्तमान मूल्य के अनुरूप कई बार पलटें। यदि यह हर बार शीर्ष पर आता है, तो काउंटर बढ़ाएँ। अन्यथा, इसे न बढ़ाएं.

इसे कंप्यूटर पर सुगमता से हासिल किया जा सकता है। होने देना $c$ काउंटर का वर्तमान मूल्य हो. उत्पादक $c$ छद्म-यादृच्छिक बिट्स और उन सभी बिट्स के तार्किक संयोजन का उपयोग करके परिणाम को काउंटर पर जोड़ें। चूंकि परिणाम शून्य था यदि उन छद्म-यादृच्छिक बिट्स में से कोई भी शून्य है, तो वृद्धि की संभावना प्राप्त होती है $2^{-c}$ . यह प्रक्रिया हर बार काउंटर बढ़ाने के लिए अनुरोध किए जाने पर निष्पादित की जाती है।

अनुप्रयोग

एल्गोरिदम पैटर्न के लिए बड़ी डेटा स्ट्रीम की जांच करने में उपयोगी है। यह विशेष रूप से डेटा संपीड़न, दृष्टि और ध्वनि पहचान और अन्य कृत्रिम बुद्धिमत्ता अनुप्रयोगों में उपयोगी है।

यह भी देखें

हाइपरलॉगलॉग

संदर्भ

↑ Nelson, Jelani; Yu, Huacheng (2020). "अनुमानित गिनती के लिए इष्टतम सीमाएँ". arXiv:2010.02116. {{cite journal}}: Cite journal requires |journal= (help)
↑ Tsidon, Erez, Iddo Hanniel, and Isaac Keslassy. "Estimators also need shared values to grow together." INFOCOM, 2012 Proceedings IEEE. IEEE, 2012.
↑ Einziger, G.; Fellman, B.; Kassner, Y. (April 2015). "Independent counter estimation buckets". 2015 IEEE Conference on Computer Communications (INFOCOM). pp. 2560–2568. doi:10.1109/INFOCOM.2015.7218646. ISBN 978-1-4799-8381-0. S2CID 15673730.

स्रोत

मॉरिस, आर. बड़ी संख्या में घटनाओं को लघु रजिस्टरों में गिनना। एसीएम 21, 10 (1978), 840-842 के संचार
फ़्लैजोलेट, पी. अनुमानित गणना: एक विस्तृत विश्लेषण। बीआईटी 25, (1985), 113-134 [1]
फाउच्स, एम., ली, सी-के., प्रोडिंगर, एच., पॉइसन-लाप्लेस-मेलिन विधि के माध्यम से अनुमानित गणना .edu.tw/~mfuchs/approx_count_3.pdf

श्रेणी:यादृच्छिक एल्गोरिदम

[ny2020-1] Nelson, Jelani; Yu, Huacheng (2020). "अनुमानित गिनती के लिए इष्टतम सीमाएँ". arXiv:2010.02116. {{cite journal}}: Cite journal requires |journal= (help)

[2] Tsidon, Erez, Iddo Hanniel, and Isaac Keslassy. "Estimators also need shared values to grow together." INFOCOM, 2012 Proceedings IEEE. IEEE, 2012.

[3] Einziger, G.; Fellman, B.; Kassner, Y. (April 2015). "Independent counter estimation buckets". 2015 IEEE Conference on Computer Communications (INFOCOM). pp. 2560–2568. doi:10.1109/INFOCOM.2015.7218646. ISBN 978-1-4799-8381-0. S2CID 15673730.

[1]

[2]

[3]