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

Revision as of 09:21, 3 August 2023

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

शब्दावली

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

एल्गोरिदम

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

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

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

संचालन

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

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

जोड़ें

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

{\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b}\rangle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j],\rho (w))\\\end{aligned}}

काउंट

काउंट एल्गोरिथ्म में $m$ रजिस्टरों के हार्मोनिक माध्य की गणना करना और काउंट का अनुमान ${\textstyle E}$ प्राप्त करने के लिए एक स्थिरांक का उपयोग करना सम्मिलित है:

Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}

\alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}}\right)\right)^{m}\,du\right)^{-1}

E=\alpha _{m}m^{2}Z

अंतर्ज्ञान यह है कि $n$ , $M$ की अज्ञात कार्डिनैलिटी होने के कारण, प्रत्येक उपसमुच्चय ${\textstyle M_{j}}$ में ${\textstyle n/m}$ तत्व होंगे। फिर अधिकतम ${\textstyle \max _{x\in M_{j}}\rho (x)}$ $log Subscript 2 Baseline left parenthesis n divided by m right parenthesis$

[1]

[2]

[3]

[4]

@@ 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++==
-हाइपरलॉगलॉग++ एल्गोरिदम मेमोरी आवश्यकताओं को कम करने और कार्डिनलिटी की कुछ श्रेणियों में सटीकता बढ़ाने के लिए हाइपरलॉगलॉग एल्गोरिदम में कई सुधारों का प्रस्ताव करता है:<ref name="Heule13"/>
+हाइपरलॉगलॉग++ एल्गोरिदम मेमोरी आवश्यकताओं को कम करने और कार्डिनलिटी की कुछ श्रेणियों में शुद्धता बढ़ाने के लिए हाइपरलॉगलॉग एल्गोरिदम में कई सुधारों का प्रस्ताव करता है:<ref name="Heule13"/>
 * मूल पेपर में प्रयुक्त 32 बिट्स के स्थान पर 64-बिट हैश फ़ंक्शन का उपयोग किया जाता है। यह बड़ी कार्डिनैलिटी के लिए हैश टकराव को कम करता है जिससे बड़ी रेंज के सुधार को हटाया जा सकता है।
@@ Line 92: / Line 92: @@
 ==स्ट्रीमिंग एचएलएल==
 जब डेटा ही स्ट्रीम में आता है, तो ऐतिहासिक व्युत्क्रम संभावना या मार्टिंगेल अनुमानक<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>

Anonymous

Search

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

Namespaces

More

Page actions