हाइपरलॉगलॉग

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

शब्दावली

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

एल्गोरिदम

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

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

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

संचालन

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

हाइपरलॉगलॉग का डेटा सरणी में संग्रहीत है M का m काउंटर (या रजिस्टर) जिन्हें 0. ऐरे से आरंभ किया गया है M मल्टीसेट से प्रारंभ किया गया S को S का हाइपरलॉगलॉग स्केच कहा जाता है।

जोड़ें

ऐड ऑपरेशन में इनपुट डेटा के हैश की गणना शामिल है v हैश फ़ंक्शन के साथ h, प्रथम प्राप्त करना 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 \alpha _{m}}$ में मौजूद व्यवस्थित गुणात्मक पूर्वाग्रह को ठीक करने के लिए पेश किया गया है ${\textstyle m^{2}Z}$ हैश टकराव के कारण.

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

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

$\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}$. मूल पेपर छोटी कार्डिनैलिटी के लिए अलग एल्गोरिदम का उपयोग करने का प्रस्ताव करता है जिसे लीनियर काउंटिंग के रूप में जाना जाता है। ऐसे मामले में जहां ऊपर दिया गया अनुमान सीमा से कम है ${\textstyle E<{\frac {5}{2}}m}$, वैकल्पिक गणना का उपयोग किया जा सकता है:

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

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

$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 )$ नमूना का उपयोग किया जाता है, जो प्राप्त करने के लिए आवश्यक स्थान का विश्लेषण करता है $1\pm \epsilon$ निश्चित सफलता संभावना के साथ सन्निकटन $1-\delta$. HLL की सापेक्ष त्रुटि है $1.04/{\sqrt {m}}$ और इसकी जरूरत है $O(\epsilon ^{-2}\log \log n+\log n)$ स्थान, कहाँ n सेट कार्डिनैलिटी है और m रजिस्टरों की संख्या है (आमतौर पर बाइट आकार से कम)।

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

गिनती और मर्ज ऑपरेशन रजिस्टरों की संख्या पर निर्भर करते हैं m और इसकी सैद्धांतिक लागत है $O(m)$. कुछ कार्यान्वयन में (रेडिस) रजिस्टरों की संख्या निश्चित की जाती है और लागत पर विचार किया जाता है $O(1)$ दस्तावेज़ीकरण में.

HLL++

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

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

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

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

एकल स्ट्रीम परिदृश्य एचएलएल स्केच निर्माण में भी बदलाव की ओर ले जाता है। एचएलएल-टेलकट+ मूल एचएलएल स्केच की तुलना में 45% कम मेमोरी का उपयोग करता है, किन्तु डेटा प्रविष्टि क्रम पर निर्भर होने और स्केच को मर्ज करने में सक्षम नहीं होने की कीमत पर।

अग्रिम पठन

• "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.