हाइपरलॉगलॉग

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

${\mathrm{\alpha <!--\; \alpha \; -->}}_m\approx <!--\; \approx \; -->\{\begin{array}{l}0.673,\end{array}$