हाइपरलॉगलॉग

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

शब्दावली

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

एल्गोरिदम

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

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

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

संचालन

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

हाइपरलॉगलॉग का डेटा 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}}$ की गणना करना आसान नहीं है, और सूत्र के साथ इसका अनुमान लगाया जा सकता है

$\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)}$

इसके अतिरिक्त, रजिस्टरों के आकार की सीमा (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 )$ मॉडल का उपयोग किया जाता है, जो एक निश्चित सफलता संभावना $1-\delta$ के साथ $1\pm \epsilon$ सन्निकटन प्राप्त करने के लिए आवश्यक स्थान का विश्लेषण करता है। एचएलएल की सापेक्ष त्रुटि $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.