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

Revision as of 10:10, 4 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)}$ ${\textstyle \log _{2}(n/m)}$ के निकट होना चाहिए। इन मात्राओं के लिए 2 का हार्मोनिक माध्य ${\textstyle mZ}$ है जो ${\textstyle n/m}$ के निकट होना चाहिए। इस प्रकार, ${\textstyle m^{2}Z}$ लगभग $n$ होना चाहिए। अंत में, हैश टकराव के कारण ${\textstyle m^{2}Z}$ में उपस्थित व्यवस्थित गुणक पूर्वाग्रह को ठीक करने के लिए स्थिरांक ${\textstyle \alpha _{m}}$ प्रस्तुत किया गया है।

व्यावहारिक विचार

स्थिरांक ${\textstyle \alpha _{m}}$ की गणना करना आसान नहीं है, और सूत्र के साथ इसका अनुमान लगाया जा सकता है^[1]

\alpha _{m}\approx {\begin{cases}0.673,&{\text{for }}m=16;\\0.697,&{\text{for }}m=32;\\0.709,&{\text{for }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{\text{for }}m\geq 128.\end{cases}}

चूँकि, हाइपरलॉगलॉग विधि ${\textstyle {\frac {5}{2}}m}$ की सीमा से नीचे की छोटी कार्डिनैलिटी के लिए पक्षपाती है। मूल पेपर छोटी कार्डिनिटी के लिए एक अलग एल्गोरिदम का उपयोग करने का प्रस्ताव करता है जिसे लीनियर काउंटिंग के रूप में जाना जाता है।^[5] ऐसे स्थितिमें जहां ऊपर दिया गया अनुमान सीमा ${\textstyle E<{\frac {5}{2}}m}$ से कम है, वैकल्पिक गणना का उपयोग किया जा सकता है:

मान लीजिये ${\textstyle V}$ रजिस्टरों की काउंटी 0 के सामान्तर हो।
यदि ${\textstyle V=0}$ , तब ऊपर दिए गए मानक हाइपरलॉग अनुमानक ${\textstyle E}$ का उपयोग करें।
अन्यथा, रैखिक गणना का उपयोग करें: ${\textstyle E^{\star }=m\log \left({\frac {m}{V}}\right)}$

इसके अतिरिक्त, रजिस्टरों के आकार की सीमा (32-बिट रजिस्टरों के लिए ${\textstyle E>{\frac {2^{32}}{30}}}$ ) के निकट पहुंचने वाली बहुत बड़ी कार्डिनैलिटी के लिए, कार्डिनैलिटी का अनुमान लगाया जा सकता है:

E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}}\right)

निचली और ऊपरी सीमाओं के लिए उपरोक्त सुधारों के साथ, त्रुटि का अनुमान ${\textstyle \sigma =1.04/{\sqrt {m}}}$ के रूप में लगाया जा सकता है।

मर्ज

दो HILLs ( ${\textstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2}}$ ) के लिए मर्ज ऑपरेशन में रजिस्टरों की प्रत्येक जोड़ी के लिए अधिकतम ${\textstyle j:1..m}$ प्राप्त करना सम्मिलित है

{\mathit {hll}}_{\text{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])

जटिलता

जटिलता का विश्लेषण करने के लिए, डेटा स्ट्रीमिंग $(\epsilon ,\delta )$ मॉडल^[6] का उपयोग किया जाता है, जो एक निश्चित सफलता संभावना $1-\delta$ के साथ $1\pm \epsilon$ सन्निकटन प्राप्त करने के लिए आवश्यक स्थान का विश्लेषण करता है। एचएलएल की सापेक्ष त्रुटि $1.04/{\sqrt {m}}$ है और इसे $O(\epsilon ^{-2}\log \log n+\log n)$ स्थान की आवश्यकता है, जहां $n$ समुच्चय कार्डिनैलिटी है और $m$ रजिस्टरों (सामान्यतः एक बाइट आकार से कम) की संख्या है ।

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

काउंटी और मर्ज ऑपरेशन रजिस्टर $m$ की संख्या पर निर्भर करते हैं और $O(m)$ की सैद्धांतिक निवेश होती है। कुछ कार्यान्वयन (रेडिस)^[7] में रजिस्टरों की संख्या निश्चित की जाती है और दस्तावेज़ीकरण में निवेश को $O(1)$ माना जाता है।

HLL++

हाइपरलॉगलॉग++ एल्गोरिदम मेमोरी आवश्यकताओं को कम करने और कार्डिनलिटी की कुछ श्रेणियों में शुद्धता बढ़ाने के लिए हाइपरलॉगलॉग एल्गोरिदम में अनेक सुधारों का प्रस्ताव करता है:^[6]

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

स्ट्रीमिंग एचएलएल

जब डेटा ही स्ट्रीम में आता है, तब ऐतिहासिक व्युत्क्रम संभावना या मार्टिंगेल अनुमानक^[8]^[9] एचएलएल स्केच की शुद्धता में उल्लेखनीय रूप से सुधार होता है और किसी दिए गए त्रुटि स्तर को प्राप्त करने के लिए 36% कम मेमोरी का उपयोग होता है। यह अनुमानक ही स्ट्रीम पर किसी भी डुप्लिकेट असंवेदनशील अनुमानित विशिष्ट काउंटी स्केच के लिए संभवतः इष्टतम है।

एकल स्ट्रीम परिदृश्य एचएलएल स्केच निर्माण में भी बदलाव की ओर ले जाता है।

एचएलएल-टेलकट+ डेटा प्रविष्टि क्रम पर निर्भर होने और स्केच को मर्ज करने में सक्षम नहीं होने की कीमत पर, किन्तु मूल एचएलएल स्केच की तुलना में 45% कम मेमोरी का उपयोग करता है।^[10]

अग्रिम पठन

"Probabilistic Data Structures for Web Analytics and Data Mining". highlyscalable.wordpress.com. May 2012. Retrieved 2014-04-19.
"New cardinality estimation algorithms for HyperLogLog sketches" (PDF). Retrieved 2016-10-29.

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm" (PDF). Discrete Mathematics and Theoretical Computer Science Proceedings. Nancy, France. AH: 137–156. CiteSeerX 10.1.1.76.4286. Retrieved 2016-12-11.
↑ Durand, M.; Flajolet, P. (2003). "बड़ी कार्डिनैलिटी की लॉगलॉग गणना।" (PDF). In G. Di Battista and U. Zwick (ed.). Lecture Notes in Computer Science. Annual European Symposium on Algorithms (ESA03). Vol. 2832. Springer. pp. 605–617.
↑ Flajolet, Philippe; Martin, G. Nigel (1985). "डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम" (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8.
↑ S Heule, M Nunkesser, A Hall (2013). "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm" (PDF). sec 4.{{cite web}}: CS1 maint: uses authors parameter (link)
↑ Whang, Kyu-Young; Vander-Zanden, Brad T; Taylor, Howard M (1990). "डेटाबेस अनुप्रयोगों के लिए एक रैखिक-समय संभाव्य गणना एल्गोरिथ्म". ACM Transactions on Database Systems. 15 (2): 208–229. doi:10.1145/78922.78925. S2CID 2939101.
↑ ^6.0 ^6.1 "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm". Retrieved 2014-04-19.
↑ "PFCOUNT – Redis".
↑ Cohen, E. (March 2015). "All-distances sketches, revisited: HIP estimators for massive graphs analysis". IEEE Transactions on Knowledge and Data Engineering. 27 (9): 2320–2334. arXiv:1306.3284. doi:10.1109/TKDE.2015.2411606.
↑ Ting, D. (August 2014). "Streamed approximate counting of distinct elements: beating optimal batch methods". Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14): 442–451. doi:10.1145/2623330.2623669. ISBN 9781450329569. S2CID 13179875.
↑ Xiao, Q.; Zhou, Y.; Chen, S. (May 2017). "Better with fewer bits: Improving the performance of cardinality estimation of large data streams". IEEE INFOCOM 2017 - IEEE Conference on Computer Communications. pp. 1–9. doi:10.1109/INFOCOM.2017.8057088. ISBN 978-1-5090-5336-0. S2CID 27159273.

[flajolet07-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 Flajolet, Philippe; Fusy, Éric; Gandouet, Olivier; Meunier, Frédéric (2007). "Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm" (PDF). Discrete Mathematics and Theoretical Computer Science Proceedings. Nancy, France. AH: 137–156. CiteSeerX 10.1.1.76.4286. Retrieved 2016-12-11.

[2] Durand, M.; Flajolet, P. (2003). "बड़ी कार्डिनैलिटी की लॉगलॉग गणना।" (PDF). In G. Di Battista and U. Zwick (ed.). Lecture Notes in Computer Science. Annual European Symposium on Algorithms (ESA03). Vol. 2832. Springer. pp. 605–617.

[3] Flajolet, Philippe; Martin, G. Nigel (1985). "डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम" (PDF). Journal of Computer and System Sciences. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8.

[4] S Heule, M Nunkesser, A Hall (2013). "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm" (PDF). sec 4.{{cite web}}: CS1 maint: uses authors parameter (link)

[5] Whang, Kyu-Young; Vander-Zanden, Brad T; Taylor, Howard M (1990). "डेटाबेस अनुप्रयोगों के लिए एक रैखिक-समय संभाव्य गणना एल्गोरिथ्म". ACM Transactions on Database Systems. 15 (2): 208–229. doi:10.1145/78922.78925. S2CID 2939101.

[Heule13-6] 6.0 ^6.1 "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm". Retrieved 2014-04-19.

[7] "PFCOUNT – Redis".

[8] Cohen, E. (March 2015). "All-distances sketches, revisited: HIP estimators for massive graphs analysis". IEEE Transactions on Knowledge and Data Engineering. 27 (9): 2320–2334. arXiv:1306.3284. doi:10.1109/TKDE.2015.2411606.

[9] Ting, D. (August 2014). "Streamed approximate counting of distinct elements: beating optimal batch methods". Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '14): 442–451. doi:10.1145/2623330.2623669. ISBN 9781450329569. S2CID 13179875.

[10] Xiao, Q.; Zhou, Y.; Chen, S. (May 2017). "Better with fewer bits: Improving the performance of cardinality estimation of large data streams". IEEE INFOCOM 2017 - IEEE Conference on Computer Communications. pp. 1–9. doi:10.1109/INFOCOM.2017.8057088. ISBN 978-1-5090-5336-0. S2CID 27159273.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{Short description|Approximate distinct counting algorithm}}
 {{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>
@@ Line 57: / Line 57: @@
 \end{cases}
 </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>
 इसके अतिरिक्त, रजिस्टरों के आकार की सीमा (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-\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>(\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-बिट हैश फ़ंक्शन का उपयोग किया जाता है। यह बड़ी कार्डिनैलिटी के लिए हैश टकराव को कम करता है जिससे बड़ी रेंज के सुधार को हटाया जा सकता है।
+* मूल पेपर में प्रयुक्त 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> एचएलएल स्केच की शुद्धता में उल्लेखनीय रूप से सुधार होता है और किसी दिए गए त्रुटि स्तर को प्राप्त करने के लिए 36% कम मेमोरी का उपयोग होता है। यह अनुमानक ही स्ट्रीम पर किसी भी डुप्लिकेट असंवेदनशील अनुमानित विशिष्ट काउंटी स्केच के लिए संभवतः इष्टतम है।

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:10, 4 August 2023

Contents

शब्दावली

एल्गोरिदम