हाइपरलॉगलॉग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Approximate distinct counting algorithm}}
{{Short description|Approximate distinct counting algorithm}}
{{Probabilistic}}
{{Probabilistic}}
हाइपरलॉगलॉग [[गिनती-विशिष्ट समस्या|काउंट-डिस्टिंक्ट समस्या]] के लिए एक एल्गोरिदम है, जो [[मल्टीसेट]] में भिन्न-भिन्न तत्वों की संख्या का अनुमान लगाता है।<ref name="flajolet07">{{cite journal |citeseerx=10.1.1.76.4286 |first1=Philippe |last1=Flajolet |first2=Éric |last2=Fusy |first3=Olivier |last3=Gandouet |first4=Frédéric |last4=Meunier |title=Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm |url=http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf |access-date=2016-12-11 |year=2007 |volume=AH
हाइपरलॉगलॉग [[गिनती-विशिष्ट समस्या|काउंट-डिस्टिंक्ट समस्या]] के लिए एक एल्गोरिदम है, जो [[मल्टीसेट|मल्टीसमुच्चय]] में भिन्न-भिन्न तत्वों की संख्या का अनुमान लगाता है।<ref name="flajolet07">{{cite journal |citeseerx=10.1.1.76.4286 |first1=Philippe |last1=Flajolet |first2=Éric |last2=Fusy |first3=Olivier |last3=Gandouet |first4=Frédéric |last4=Meunier |title=Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm |url=http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf |access-date=2016-12-11 |year=2007 |volume=AH
|pages=137–156 |journal=Discrete Mathematics and Theoretical Computer Science Proceedings |location=[[Nancy, France]]}} <!-- Note DMTCS published this in their conference proc. instead of their main journal, but the specific conference is not relevant – not like that's where it was first presented before submission, or where the algorithm got used: conf=AOFA ’07: Proceedings of the 2007 International Conference on the Analysis of Algorithms --></ref> मल्टीसेट के भिन्न-भिन्न तत्वों की सटीक [[प्रमुखता|कार्डिनैलिटी]] की गणना के लिए कार्डिनैलिटी के अनुपात में मेमोरी की मात्रा की आवश्यकता होती है, जो बहुत बड़े डेटा सेट के लिए अव्यावहारिक है। हाइपरलॉगलॉग एल्गोरिदम जैसे संभाव्य कार्डिनैलिटी अनुमानक, इससे काफी कम मेमोरी का उपयोग करते हैं, किन्तु केवल कार्डिनैलिटी का अनुमान लगा सकते हैं। हाइपरलॉगलॉग एल्गोरिदम 1.5 केबी मेमोरी का उपयोग करके 2% की विशिष्ट शुद्धता (मानक त्रुटि) के साथ > 10<sup>9</sup> की कार्डिनैलिटी का अनुमान लगाने में सक्षम है।<ref name="flajolet07"/> हाइपरलॉगलॉग पहले के लॉगलॉग एल्गोरिदम का एक विस्तार है,<ref>{{cite conference |url=http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf |title=बड़ी कार्डिनैलिटी की लॉगलॉग गणना।|last1=Durand |first1=M. |last2=Flajolet |first2=P. |date=2003 |publisher=Springer |editor=G. Di Battista and U. Zwick |conference = Annual European Symposium on Algorithms (ESA03)|book-title=Lecture Notes in Computer Science |volume=2832 |pages=605–617}}</ref> जो स्वयं 1984 फ्लैजोलेट-मार्टिन एल्गोरिदम से प्राप्त हुआ है।<ref>{{Cite journal |doi=10.1016/0022-0000(85)90041-8 |title=डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम|journal=Journal of Computer and System Sciences |volume=31 |issue=2 |pages=182&ndash;209 |year=1985 |last1=Flajolet |first1=Philippe |last2=Martin |first2=G. Nigel |url=http://algo.inria.fr/flajolet/Publications/FlMa85.pdf}}</ref>
|pages=137–156 |journal=Discrete Mathematics and Theoretical Computer Science Proceedings |location=[[Nancy, France]]}} <!-- Note DMTCS published this in their conference proc. instead of their main journal, but the specific conference is not relevant – not like that's where it was first presented before submission, or where the algorithm got used: conf=AOFA ’07: Proceedings of the 2007 International Conference on the Analysis of Algorithms --></ref> मल्टीसमुच्चय के भिन्न-भिन्न तत्वों की त्रुटिहीन [[प्रमुखता|कार्डिनैलिटी]] की गणना के लिए कार्डिनैलिटी के अनुपात में मेमोरी की मात्रा की आवश्यकता होती है, जो बहुत बड़े डेटा समुच्चय के लिए अव्यावहारिक है। हाइपरलॉगलॉग एल्गोरिदम जैसे संभाव्य कार्डिनैलिटी अनुमानक, इससे अधिक कम मेमोरी का उपयोग करते हैं, किन्तु केवल कार्डिनैलिटी का अनुमान लगा सकते हैं। हाइपरलॉगलॉग एल्गोरिदम 1.5 केबी मेमोरी का उपयोग करके 2% की विशिष्ट शुद्धता (मानक त्रुटि) के साथ > 10<sup>9</sup> की कार्डिनैलिटी का अनुमान लगाने में सक्षम है।<ref name="flajolet07"/> हाइपरलॉगलॉग पहले के लॉगलॉग एल्गोरिदम का एक विस्तार है,<ref>{{cite conference |url=http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf |title=बड़ी कार्डिनैलिटी की लॉगलॉग गणना।|last1=Durand |first1=M. |last2=Flajolet |first2=P. |date=2003 |publisher=Springer |editor=G. Di Battista and U. Zwick |conference = Annual European Symposium on Algorithms (ESA03)|book-title=Lecture Notes in Computer Science |volume=2832 |pages=605–617}}</ref> जो स्वयं 1984 फ्लैजोलेट-मार्टिन एल्गोरिदम से प्राप्त हुआ है।<ref>{{Cite journal |doi=10.1016/0022-0000(85)90041-8 |title=डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम|journal=Journal of Computer and System Sciences |volume=31 |issue=2 |pages=182&ndash;209 |year=1985 |last1=Flajolet |first1=Philippe |last2=Martin |first2=G. Nigel |url=http://algo.inria.fr/flajolet/Publications/FlMa85.pdf}}</ref>




==शब्दावली==
==शब्दावली==
फ्लैजोलेट एट अल<ref name="flajolet07"/> द्वारा मूल पेपर में और काउंटी-विशिष्ट समस्या पर संबंधित साहित्य में, कार्डिनैलिटी शब्द का उपयोग दोहराए गए तत्वों के साथ डेटा स्ट्रीम में भिन्न-भिन्न तत्वों की संख्या के लिए किया जाता है। चूँकि मल्टीसेट के सिद्धांत में यह शब्द मल्टीसेट के प्रत्येक सदस्य की बहुलता के योग को संदर्भित करता है। यह आलेख स्रोतों के साथ एकरूपता के लिए फ्लैजोलेट की परिभाषा का उपयोग करना चुनता है।
फ्लैजोलेट एट अल<ref name="flajolet07"/> द्वारा मूल पेपर में और काउंटी-विशिष्ट समस्या पर संबंधित साहित्य में, कार्डिनैलिटी शब्द का उपयोग दोहराए गए तत्वों के साथ डेटा स्ट्रीम में भिन्न-भिन्न तत्वों की संख्या के लिए किया जाता है। चूँकि मल्टीसमुच्चय के सिद्धांत में यह शब्द मल्टीसमुच्चय के प्रत्येक सदस्य की बहुलता के योग को संदर्भित करता है। यह आलेख स्रोतबं के साथ एकरूपता के लिए फ्लैजोलेट की परिभाषा का उपयोग करना चुनता है।


==एल्गोरिदम==
==एल्गोरिदम==
हाइपरलॉगलॉग एल्गोरिदम का आधार यह अवलोकन है कि सेट में प्रत्येक संख्या के बाइनरी प्रतिनिधित्व में अग्रणी शून्य की अधिकतम संख्या की गणना करके समान रूप से वितरित यादृच्छिक संख्याओं के मल्टीसेट की कार्डिनैलिटी का अनुमान लगाया जा सकता है। यदि देखे गए अग्रणी शून्यों की अधिकतम संख्या n है, तो सेट में भिन्न-भिन्न तत्वों की संख्या का अनुमान 2<sup>n</sup> है।<ref name="flajolet07"/>
हाइपरलॉगलॉग एल्गोरिदम का आधार यह अवलोकन है कि समुच्चय में प्रत्येक संख्या के बाइनरी प्रतिनिधित्व में अग्रणी शून्य की अधिकतम संख्या की गणना करके समान रूप से वितरित यादृच्छिक संख्याओं के मल्टीसमुच्चय की कार्डिनैलिटी का अनुमान लगाया जा सकता है। यदि देखे गए अग्रणी शून्यों की अधिकतम संख्या n है, तब समुच्चय में भिन्न-भिन्न तत्वों की संख्या का अनुमान 2<sup>n</sup> है।<ref name="flajolet07"/>


हाइपरलॉगलॉग एल्गोरिदम में, मूल मल्टीसेट के समान कार्डिनैलिटी के साथ समान रूप से वितरित यादृच्छिक संख्याओं का मल्टीसेट प्राप्त करने के लिए मूल मल्टीसेट में प्रत्येक तत्व पर [[हैश फंकशन]] लागू किया जाता है। इस अव्यवस्थित ढंग से वितरित सेट की प्रमुखता का अनुमान उपरोक्त एल्गोरिदम का उपयोग करके लगाया जा सकता है।
हाइपरलॉगलॉग एल्गोरिदम में, मूल मल्टीसमुच्चय के समान कार्डिनैलिटी के साथ समान रूप से वितरित यादृच्छिक संख्याओं का मल्टीसमुच्चय प्राप्त करने के लिए मूल मल्टीसमुच्चय में प्रत्येक तत्व पर [[हैश फंकशन]] प्रयुक्त किया जाता है। इस अव्यवस्थित ढंग से वितरित समुच्चय की प्रमुखता का अनुमान उपरोक्त एल्गोरिदम का उपयोग करके लगाया जा सकता है।


उपरोक्त एल्गोरिदम का उपयोग करके प्राप्त कार्डिनैलिटी के सरल अनुमान में बड़े भिन्नता का हानि है। हाइपरलॉगलॉग एल्गोरिथ्म में, मल्टीसेट को कई उपसमूहों में विभाजित करके, इनमें से प्रत्येक उपसमूह में संख्याओं में अग्रणी शून्य की अधिकतम संख्या की गणना करके और प्रत्येक उपसमूह के लिए इन अनुमानों को कार्डिनैलिटी के अनुमान में संयोजित करने के लिए [[अनुकूल माध्य|हार्मोनिक माध्य]] का उपयोग करके भिन्नता को कम किया जाता है।<ref>{{Cite web |url=https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf |title=HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm |authors=S Heule, M Nunkesser, A Hall |year=2013 |at=sec 4}}</ref>
उपरोक्त एल्गोरिदम का उपयोग करके प्राप्त कार्डिनैलिटी के सरल अनुमान में बड़े भिन्नता का हानि है। हाइपरलॉगलॉग एल्गोरिथ्म में, मल्टीसमुच्चय को अनेक उपसमूहों में विभाजित करके, इनमें से प्रत्येक उपसमूह में संख्याओं में अग्रणी शून्य की अधिकतम संख्या की गणना करके और प्रत्येक उपसमूह के लिए इन अनुमानों को कार्डिनैलिटी के अनुमान में संयोजित करने के लिए [[अनुकूल माध्य|हार्मोनिक माध्य]] का उपयोग करके भिन्नता को कम किया जाता है।<ref>{{Cite web |url=https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf |title=HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm |authors=S Heule, M Nunkesser, A Hall |year=2013 |at=sec 4}}</ref>
==संचालन==
==संचालन==
हाइपरलॉगलॉग के तीन मुख्य ऑपरेशन हैं: सेट में नया तत्व जोड़ने के लिए जोड़ें, सेट की कार्डिनैलिटी प्राप्त करने के लिए गिनें और दो सेटों का मिलन प्राप्त करने के लिए मर्ज करें। कुछ व्युत्पन्न परिचालनों की गणना समावेशन-बहिष्करण सिद्धांत का उपयोग करके की जा सकती है जैसे कि प्रतिच्छेदन की कार्डिनैलिटी या मर्ज और काउंटी संचालन के संयोजन वाले दो हाइपरलॉगलॉग के बीच अंतर की कार्डिनैलिटी।
हाइपरलॉगलॉग के तीन मुख्य ऑपरेशन हैं: समुच्चय में नया तत्व जोड़ने के लिए जोड़ें, समुच्चय की कार्डिनैलिटी प्राप्त करने के लिए गिनें और दो समुच्चयों का मिलन प्राप्त करने के लिए मर्ज करें। कुछ व्युत्पन्न परिचालनों की गणना समावेशन-बहिष्करण सिद्धांत का उपयोग करके की जा सकती है जैसे कि प्रतिच्छेदन की कार्डिनैलिटी या मर्ज और काउंटी संचालन के संयोजन वाले दो हाइपरलॉगलॉग के मध्य अंतर की कार्डिनैलिटी।


हाइपरलॉगलॉग का डेटा {{mvar|M}} काउंटरों (या "रजिस्टर") के एरे {{mvar|m}} में संग्रहीत होता है, जिसे 0 से प्रारंभ किया जाता है। मल्टीसेट ''S'' से प्रारंभ किए गए एरे {{mvar|M}} को {{mvar|S}} का हाइपरलॉगलॉग स्केच कहा जाता है।
हाइपरलॉगलॉग का डेटा {{mvar|M}} काउंटरों (या "रजिस्टर") के एरे {{mvar|m}} में संग्रहीत होता है, जिसे 0 से प्रारंभ किया जाता है। मल्टीसमुच्चय ''S'' से प्रारंभ किए गए एरे {{mvar|M}} को {{mvar|S}} का हाइपरलॉगलॉग स्केच कहा जाता है।


===जोड़ें===
===जोड़ें===
ऐड ऑपरेशन में हैश फ़ंक्शन {{mvar|h}} के साथ इनपुट डेटा {{mvar|v}} के हैश की गणना करना, पहले b बिट्स (जहां {{mvar|b}} <math display="inline">\log_2(m)</math> है) प्राप्त करना और संशोधित करने के लिए रजिस्टर का पता प्राप्त करने के लिए उनमें 1 जोड़ना सम्मिलित है। शेष बिट्स के साथ <math display="inline">\rho(w)</math> की गणना करें जो सबसे बाईं ओर 1 की स्थिति लौटाता है। रजिस्टर का नया मान रजिस्टर के वर्तमान मान और <math display="inline">\rho(w)</math> के बीच अधिकतम होगा।
ऐड ऑपरेशन में हैश फलन {{mvar|h}} के साथ इनपुट डेटा {{mvar|v}} के हैश की गणना करना, पहले b बिट्स (जहां {{mvar|b}} <math display="inline">\log_2(m)</math> है) प्राप्त करना और संशोधित करने के लिए रजिस्टर का पता प्राप्त करने के लिए उनमें 1 जोड़ना सम्मिलित है। शेष बिट्स के साथ <math display="inline">\rho(w)</math> की गणना करें जो सबसे बाईं ओर 1 की स्थिति लौटाता है। रजिस्टर का नया मान रजिस्टर के वर्तमान मान और <math display="inline">\rho(w)</math> के मध्य अधिकतम होगा।


:<math>
:<math>
Line 57: Line 57:
\end{cases}
\end{cases}
</math>
</math>
हालाँकि, हाइपरलॉगलॉग विधि <math display="inline">\frac{5}{2}m</math> की सीमा से नीचे की छोटी कार्डिनैलिटी के लिए पक्षपाती है। मूल पेपर छोटी कार्डिनिटी के लिए एक अलग एल्गोरिदम का उपयोग करने का प्रस्ताव करता है जिसे लीनियर काउंटिंग के रूप में जाना जाता है।<ref>{{Cite journal |title=डेटाबेस अनुप्रयोगों के लिए एक रैखिक-समय संभाव्य गणना एल्गोरिथ्म|journal=ACM Transactions on Database Systems |volume=15 |number=2 |pages=208&ndash;229 |year=1990 |last1=Whang |first1= Kyu-Young  |last2= Vander-Zanden |first2=Brad T|last3=Taylor |first3=Howard M |doi=10.1145/78922.78925 |s2cid=2939101 }}</ref> ऐसे स्थितिमें जहां ऊपर दिया गया अनुमान सीमा <math display="inline">E < \frac{5}{2}m</math> से कम है, वैकल्पिक गणना का उपयोग किया जा सकता है:
चूँकि, हाइपरलॉगलॉग विधि <math display="inline">\frac{5}{2}m</math> की सीमा से नीचे की छोटी कार्डिनैलिटी के लिए पक्षपाती है। मूल पेपर छोटी कार्डिनिटी के लिए एक अलग एल्गोरिदम का उपयोग करने का प्रस्ताव करता है जिसे लीनियर काउंटिंग के रूप में जाना जाता है।<ref>{{Cite journal |title=डेटाबेस अनुप्रयोगों के लिए एक रैखिक-समय संभाव्य गणना एल्गोरिथ्म|journal=ACM Transactions on Database Systems |volume=15 |number=2 |pages=208&ndash;229 |year=1990 |last1=Whang |first1= Kyu-Young  |last2= Vander-Zanden |first2=Brad T|last3=Taylor |first3=Howard M |doi=10.1145/78922.78925 |s2cid=2939101 }}</ref> ऐसे स्थितिमें जहां ऊपर दिया गया अनुमान सीमा <math display="inline">E < \frac{5}{2}m</math> से कम है, वैकल्पिक गणना का उपयोग किया जा सकता है:


# मान लीजिये <math display="inline">V</math> रजिस्टरों की काउंटी 0 के बराबर हो।
# मान लीजिये <math display="inline">V</math> रजिस्टरों की काउंटी 0 के सामान्तर हो।
# यदि <math display="inline">V = 0</math>, तो ऊपर दिए गए मानक हाइपरलॉग अनुमानक <math display="inline">E</math> का उपयोग करें।
# यदि <math display="inline">V = 0</math>, तब ऊपर दिए गए मानक हाइपरलॉग अनुमानक <math display="inline">E</math> का उपयोग करें।
# अन्यथा, रैखिक गणना का उपयोग करें: <math display="inline">E^{\star} = m\log\left(\frac{m}{V}\right)</math>
# अन्यथा, रैखिक गणना का उपयोग करें: <math display="inline">E^{\star} = m\log\left(\frac{m}{V}\right)</math>
इसके अतिरिक्त, रजिस्टरों के आकार की सीमा (32-बिट रजिस्टरों के लिए <math display="inline">E > \frac{2^{32}}{30}</math>) के निकट पहुंचने वाली बहुत बड़ी कार्डिनैलिटी के लिए, कार्डिनैलिटी का अनुमान लगाया जा सकता है:
इसके अतिरिक्त, रजिस्टरों के आकार की सीमा (32-बिट रजिस्टरों के लिए <math display="inline">E > \frac{2^{32}}{30}</math>) के निकट पहुंचने वाली बहुत बड़ी कार्डिनैलिटी के लिए, कार्डिनैलिटी का अनुमान लगाया जा सकता है:
Line 77: Line 77:


==जटिलता==
==जटिलता==
जटिलता का विश्लेषण करने के लिए, डेटा स्ट्रीमिंग <math>(\epsilon,\delta)</math> नमूना<ref name="Heule13">{{cite web|url=http://research.google.com/pubs/pub40671.html|title=HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm|access-date=2014-04-19}}</ref> का उपयोग किया जाता है, जो प्राप्त करने के लिए आवश्यक स्थान का विश्लेषण करता है <math>1\pm \epsilon</math> निश्चित सफलता संभावना के साथ सन्निकटन <math>1-\delta</math>. HLL की सापेक्ष त्रुटि है <math>1.04/\sqrt{m}</math> और इसकी जरूरत है <math>O(\epsilon^{-2} \log\log n + \log n)</math> स्थान, कहाँ {{mvar|n}} सेट कार्डिनैलिटी है और {{mvar|m}} रजिस्टरों की संख्या है (आमतौर पर बाइट आकार से कम)।
जटिलता का विश्लेषण करने के लिए, डेटा स्ट्रीमिंग <math>(\epsilon,\delta)</math> मॉडल<ref name="Heule13">{{cite web|url=http://research.google.com/pubs/pub40671.html|title=HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm|access-date=2014-04-19}}</ref> का उपयोग किया जाता है, जो एक निश्चित सफलता संभावना <math>1-\delta</math> के साथ <math>1\pm \epsilon</math> सन्निकटन प्राप्त करने के लिए आवश्यक स्थान का विश्लेषण करता है। एचएलएल की सापेक्ष त्रुटि <math>1.04/\sqrt{m}</math> है और इसे <math>O(\epsilon^{-2} \log\log n + \log n)</math> स्थान की आवश्यकता है, जहां {{mvar|n}} समुच्चय कार्डिनैलिटी है और {{mvar|m}} रजिस्टरों (सामान्यतः एक बाइट आकार से कम) की संख्या है ।


ऐड ऑपरेशन हैश फ़ंक्शन के आउटपुट के आकार पर निर्भर करता है। चूँकि यह आकार निश्चित है, हम ऐड ऑपरेशन के चलने के समय पर विचार कर सकते हैं <math>O(1)</math>.
ऐड ऑपरेशन हैश फलन के आउटपुट के आकार पर निर्भर करता है। चूँकि यह आकार निश्चित है, हम ऐड ऑपरेशन के लिए चलने के समय को <math>O(1)</math> मान सकते हैं।


काउंटी और मर्ज ऑपरेशन रजिस्टरों की संख्या पर निर्भर करते हैं {{mvar|m}} और इसकी सैद्धांतिक लागत है <math>O(m)</math>. कुछ कार्यान्वयन में ([[रेडिस]])<ref>{{Cite web | url=https://redis.io/commands/pfcount | title=PFCOUNT – Redis}}</ref> रजिस्टरों की संख्या निश्चित की जाती है और लागत पर विचार किया जाता है <math>O(1)</math> दस्तावेज़ीकरण में.
काउंटी और मर्ज ऑपरेशन रजिस्टर {{mvar|m}} की संख्या पर निर्भर करते हैं  और <math>O(m)</math> की सैद्धांतिक निवेश होती है। कुछ कार्यान्वयन ([[रेडिस]])<ref>{{Cite web | url=https://redis.io/commands/pfcount | title=PFCOUNT – Redis}}</ref> में रजिस्टरों की संख्या निश्चित की जाती है और दस्तावेज़ीकरण में निवेश को <math>O(1)</math> माना जाता है।


==HLL++==
==HLL++==
हाइपरलॉगलॉग++ एल्गोरिदम मेमोरी आवश्यकताओं को कम करने और कार्डिनलिटी की कुछ श्रेणियों में सटीकता बढ़ाने के लिए हाइपरलॉगलॉग एल्गोरिदम में कई सुधारों का प्रस्ताव करता है:<ref name="Heule13"/>
हाइपरलॉगलॉग++ एल्गोरिदम मेमोरी आवश्यकताओं को कम करने और कार्डिनलिटी की कुछ श्रेणियों में शुद्धता बढ़ाने के लिए हाइपरलॉगलॉग एल्गोरिदम में अनेक सुधारों का प्रस्ताव करता है:<ref name="Heule13"/>


* मूल पेपर में प्रयुक्त 32 बिट्स के स्थान पर 64-बिट हैश फ़ंक्शन का उपयोग किया जाता है। यह बड़ी कार्डिनैलिटी के लिए हैश टकराव को कम करता है जिससे बड़ी रेंज के सुधार को हटाया जा सकता है।
* मूल पेपर में प्रयुक्त 32 बिट्स के स्थान पर 64-बिट हैश फलन का उपयोग किया जाता है। यह बड़ी कार्डिनैलिटी के लिए हैश टकराव को कम करता है जिससे बड़ी रेंज के सुधार को हटाया जा सकता है।
* रैखिक काउंटी से एचएलएल काउंटी पर स्विच करते समय छोटी कार्डिनैलिटी के लिए कुछ पूर्वाग्रह पाए जाते हैं। समस्या को कम करने के लिए अनुभवजन्य पूर्वाग्रह सुधार प्रस्तावित है।
* रैखिक काउंटी से एचएलएल काउंटी पर स्विच करते समय छोटी कार्डिनैलिटी के लिए कुछ पूर्वाग्रह पाए जाते हैं। समस्या को कम करने के लिए अनुभवजन्य पूर्वाग्रह सुधार प्रस्तावित है।
* छोटे कार्डिनैलिटी के लिए मेमोरी आवश्यकताओं को कम करने के लिए रजिस्टरों का विरल प्रतिनिधित्व प्रस्तावित है, जिसे बाद में कार्डिनैलिटी बढ़ने पर घने प्रतिनिधित्व में बदला जा सकता है।
* छोटे कार्डिनैलिटी के लिए मेमोरी आवश्यकताओं को कम करने के लिए रजिस्टरों का विरल प्रतिनिधित्व प्रस्तावित है, जिसे पश्चात् में कार्डिनैलिटी बढ़ने पर घने प्रतिनिधित्व में बदला जा सकता है।


==स्ट्रीमिंग एचएलएल==
==स्ट्रीमिंग एचएलएल==
जब डेटा ही स्ट्रीम में आता है, तो ऐतिहासिक व्युत्क्रम संभावना या मार्टिंगेल अनुमानक<ref>{{Cite journal|last=Cohen|first=E.|date=March 2015|title=All-distances sketches, revisited: HIP estimators for massive graphs analysis|journal=IEEE Transactions on Knowledge and Data Engineering|volume=27|issue=9|pages=2320–2334|doi=10.1109/TKDE.2015.2411606|arxiv=1306.3284}}</ref><ref>
जब डेटा ही स्ट्रीम में आता है, तब ऐतिहासिक व्युत्क्रम संभावना या मार्टिंगेल अनुमानक<ref>{{Cite journal|last=Cohen|first=E.|date=March 2015|title=All-distances sketches, revisited: HIP estimators for massive graphs analysis|journal=IEEE Transactions on Knowledge and Data Engineering|volume=27|issue=9|pages=2320–2334|doi=10.1109/TKDE.2015.2411606|arxiv=1306.3284}}</ref><ref>
{{Cite journal|last=Ting|first=D.|date=August 2014|title=Streamed approximate counting of distinct elements: beating optimal batch methods.|url=https://research.fb.com/publications/streamed-approximate-counting-of-distinct-elements/|journal=Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14)|pages=442–451|doi=10.1145/2623330.2623669|isbn=9781450329569|s2cid=13179875 }}</ref>
{{Cite journal|last=Ting|first=D.|date=August 2014|title=Streamed approximate counting of distinct elements: beating optimal batch methods.|url=https://research.fb.com/publications/streamed-approximate-counting-of-distinct-elements/|journal=Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14)|pages=442–451|doi=10.1145/2623330.2623669|isbn=9781450329569|s2cid=13179875 }}</ref> एचएलएल स्केच की शुद्धता में उल्लेखनीय रूप से सुधार होता है और किसी दिए गए त्रुटि स्तर को प्राप्त करने के लिए 36% कम मेमोरी का उपयोग होता है। यह अनुमानक ही स्ट्रीम पर किसी भी डुप्लिकेट असंवेदनशील अनुमानित विशिष्ट काउंटी स्केच के लिए संभवतः इष्टतम है।
एचएलएल स्केच की सटीकता में उल्लेखनीय रूप से सुधार होता है और किसी दिए गए त्रुटि स्तर को प्राप्त करने के लिए 36% कम मेमोरी का उपयोग होता है। यह अनुमानक ही स्ट्रीम पर किसी भी डुप्लिकेट असंवेदनशील अनुमानित विशिष्ट काउंटी स्केच के लिए संभवतः इष्टतम है।


एकल स्ट्रीम परिदृश्य एचएलएल स्केच निर्माण में भी बदलाव की ओर ले जाता है।
एकल स्ट्रीम परिदृश्य एचएलएल स्केच निर्माण में भी बदलाव की ओर ले जाता है।
एचएलएल-टेलकट+ मूल एचएलएल स्केच की तुलना में 45% कम मेमोरी का उपयोग करता है, किन्तु डेटा प्रविष्टि क्रम पर निर्भर होने और स्केच को मर्ज करने में सक्षम नहीं होने की कीमत पर।<ref>{{Cite book|last1=Xiao|first1=Q.|last2=Zhou|first2=Y.|last3=Chen|first3=S.|title=IEEE INFOCOM 2017 - IEEE Conference on Computer Communications |chapter=Better with fewer bits: Improving the performance of cardinality estimation of large data streams |date=May 2017|pages=1–9|doi=10.1109/INFOCOM.2017.8057088|isbn=978-1-5090-5336-0|s2cid=27159273 }}</ref>
 
एचएलएल-टेलकट+ डेटा प्रविष्टि क्रम पर निर्भर होने और स्केच को मर्ज करने में सक्षम नहीं होने की कीमत पर, किन्तु मूल एचएलएल स्केच की तुलना में 45% कम मेमोरी का उपयोग करता है।<ref>{{Cite book|last1=Xiao|first1=Q.|last2=Zhou|first2=Y.|last3=Chen|first3=S.|title=IEEE INFOCOM 2017 - IEEE Conference on Computer Communications |chapter=Better with fewer bits: Improving the performance of cardinality estimation of large data streams |date=May 2017|pages=1–9|doi=10.1109/INFOCOM.2017.8057088|isbn=978-1-5090-5336-0|s2cid=27159273 }}</ref>




Line 106: Line 107:
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
[[Category: संभाव्य डेटा संरचनाएँ]] [[Category: सांख्यिकीय एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:CS1 maint]]
[[Category:Created On 27/07/2023]]
[[Category:Created On 27/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:संभाव्य डेटा संरचनाएँ]]
[[Category:सांख्यिकीय एल्गोरिदम]]

Latest revision as of 14:18, 14 August 2023

Part of a series on
Probabilistic
data structures
Random trees
Related

हाइपरलॉगलॉग काउंट-डिस्टिंक्ट समस्या के लिए एक एल्गोरिदम है, जो मल्टीसमुच्चय में भिन्न-भिन्न तत्वों की संख्या का अनुमान लगाता है।[1] मल्टीसमुच्चय के भिन्न-भिन्न तत्वों की त्रुटिहीन कार्डिनैलिटी की गणना के लिए कार्डिनैलिटी के अनुपात में मेमोरी की मात्रा की आवश्यकता होती है, जो बहुत बड़े डेटा समुच्चय के लिए अव्यावहारिक है। हाइपरलॉगलॉग एल्गोरिदम जैसे संभाव्य कार्डिनैलिटी अनुमानक, इससे अधिक कम मेमोरी का उपयोग करते हैं, किन्तु केवल कार्डिनैलिटी का अनुमान लगा सकते हैं। हाइपरलॉगलॉग एल्गोरिदम 1.5 केबी मेमोरी का उपयोग करके 2% की विशिष्ट शुद्धता (मानक त्रुटि) के साथ > 109 की कार्डिनैलिटी का अनुमान लगाने में सक्षम है।[1] हाइपरलॉगलॉग पहले के लॉगलॉग एल्गोरिदम का एक विस्तार है,[2] जो स्वयं 1984 फ्लैजोलेट-मार्टिन एल्गोरिदम से प्राप्त हुआ है।[3]


शब्दावली

फ्लैजोलेट एट अल[1] द्वारा मूल पेपर में और काउंटी-विशिष्ट समस्या पर संबंधित साहित्य में, कार्डिनैलिटी शब्द का उपयोग दोहराए गए तत्वों के साथ डेटा स्ट्रीम में भिन्न-भिन्न तत्वों की संख्या के लिए किया जाता है। चूँकि मल्टीसमुच्चय के सिद्धांत में यह शब्द मल्टीसमुच्चय के प्रत्येक सदस्य की बहुलता के योग को संदर्भित करता है। यह आलेख स्रोतबं के साथ एकरूपता के लिए फ्लैजोलेट की परिभाषा का उपयोग करना चुनता है।

एल्गोरिदम

हाइपरलॉगलॉग एल्गोरिदम का आधार यह अवलोकन है कि समुच्चय में प्रत्येक संख्या के बाइनरी प्रतिनिधित्व में अग्रणी शून्य की अधिकतम संख्या की गणना करके समान रूप से वितरित यादृच्छिक संख्याओं के मल्टीसमुच्चय की कार्डिनैलिटी का अनुमान लगाया जा सकता है। यदि देखे गए अग्रणी शून्यों की अधिकतम संख्या n है, तब समुच्चय में भिन्न-भिन्न तत्वों की संख्या का अनुमान 2n है।[1]

हाइपरलॉगलॉग एल्गोरिदम में, मूल मल्टीसमुच्चय के समान कार्डिनैलिटी के साथ समान रूप से वितरित यादृच्छिक संख्याओं का मल्टीसमुच्चय प्राप्त करने के लिए मूल मल्टीसमुच्चय में प्रत्येक तत्व पर हैश फंकशन प्रयुक्त किया जाता है। इस अव्यवस्थित ढंग से वितरित समुच्चय की प्रमुखता का अनुमान उपरोक्त एल्गोरिदम का उपयोग करके लगाया जा सकता है।

उपरोक्त एल्गोरिदम का उपयोग करके प्राप्त कार्डिनैलिटी के सरल अनुमान में बड़े भिन्नता का हानि है। हाइपरलॉगलॉग एल्गोरिथ्म में, मल्टीसमुच्चय को अनेक उपसमूहों में विभाजित करके, इनमें से प्रत्येक उपसमूह में संख्याओं में अग्रणी शून्य की अधिकतम संख्या की गणना करके और प्रत्येक उपसमूह के लिए इन अनुमानों को कार्डिनैलिटी के अनुमान में संयोजित करने के लिए हार्मोनिक माध्य का उपयोग करके भिन्नता को कम किया जाता है।[4]

संचालन

हाइपरलॉगलॉग के तीन मुख्य ऑपरेशन हैं: समुच्चय में नया तत्व जोड़ने के लिए जोड़ें, समुच्चय की कार्डिनैलिटी प्राप्त करने के लिए गिनें और दो समुच्चयों का मिलन प्राप्त करने के लिए मर्ज करें। कुछ व्युत्पन्न परिचालनों की गणना समावेशन-बहिष्करण सिद्धांत का उपयोग करके की जा सकती है जैसे कि प्रतिच्छेदन की कार्डिनैलिटी या मर्ज और काउंटी संचालन के संयोजन वाले दो हाइपरलॉगलॉग के मध्य अंतर की कार्डिनैलिटी।

हाइपरलॉगलॉग का डेटा M काउंटरों (या "रजिस्टर") के एरे m में संग्रहीत होता है, जिसे 0 से प्रारंभ किया जाता है। मल्टीसमुच्चय S से प्रारंभ किए गए एरे M को S का हाइपरलॉगलॉग स्केच कहा जाता है।

जोड़ें

ऐड ऑपरेशन में हैश फलन h के साथ इनपुट डेटा v के हैश की गणना करना, पहले b बिट्स (जहां b है) प्राप्त करना और संशोधित करने के लिए रजिस्टर का पता प्राप्त करने के लिए उनमें 1 जोड़ना सम्मिलित है। शेष बिट्स के साथ की गणना करें जो सबसे बाईं ओर 1 की स्थिति लौटाता है। रजिस्टर का नया मान रजिस्टर के वर्तमान मान और के मध्य अधिकतम होगा।