हाइपरलॉगलॉग

हाइपरलॉगलॉग काउंट-डिस्टिंक्ट समस्या के लिए एक एल्गोरिदम है, जो मल्टीसेट में भिन्न-भिन्न तत्वों की संख्या का अनुमान लगाता है। मल्टीसेट के भिन्न-भिन्न तत्वों की सटीक कार्डिनैलिटी की गणना के लिए कार्डिनैलिटी के अनुपात में मेमोरी की मात्रा की आवश्यकता होती है, जो बहुत बड़े डेटा सेट के लिए अव्यावहारिक है। हाइपरलॉगलॉग एल्गोरिदम जैसे संभाव्य कार्डिनैलिटी अनुमानक, इससे काफी कम मेमोरी का उपयोग करते हैं, किन्तु केवल कार्डिनैलिटी का अनुमान लगा सकते हैं। हाइपरलॉगलॉग एल्गोरिदम 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 का हार्मोनिक माध्य $m$