गणना-विशिष्ट समस्या

कंप्यूटर विज्ञान में, गिनती-विशिष्ट समस्या (अनुप्रयुक्त गणित में कार्डिनैलिटी अनुमान समस्या के रूप में भी जाना जाता है) दोहराए गए तत्वों के साथ डेटा स्ट्रीम में अलग-अलग तत्वों की संख्या खोजने की समस्या है। यह अनेक अनुप्रयोगों में एक सुविख्यात समस्या है। तत्व राउटर (कंप्यूटिंग) से गुजरने वाले पैकेट के आईपी पते, किसी वेब साइट पर अद्वितीय विज़िटर, बड़े डेटाबेस में तत्व, डीएनए अनुक्रम में रूपांकनों, या आरएफआईडी/सेंसर नेटवर्क के तत्वों का प्रतिनिधित्व कर सकते हैं।

औपचारिक परिभाषा

उदाहरण: तत्वों की एक धारा $x_{1},x_{2},\ldots ,x_{s}$ दोहराव और एक पूर्णांक के साथ $m$. होने देना $n$ अर्थात् भिन्न तत्वों की संख्या हो $n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|$, और इन तत्वों को रहने दें $\left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}$.

उद्देश्य: एक अनुमान खोजें ${\widehat {n}}$ का $n$ केवल उपयोग कर रहे हैं $m$ भंडारण इकाइयाँ, कहाँ $m\ll n$.

कार्डिनैलिटी अनुमान समस्या के उदाहरण का एक उदाहरण स्ट्रीम है: $a,b,a,c,d,b,d$. इस उदाहरण के लिए, $n=|\left\{{a,b,c,d}\right\}|=4$.

अनुचित समाधान

समस्या का सरल समाधान इस प्रकार है:

 एक काउंटर प्रारंभ करें, c, शून्य तक, $c\leftarrow 0$.
 एक कुशल शब्दकोश डेटा संरचना प्रारंभ करें, D, जैसे हैश टेबल या सर्च ट्री जिसमें प्रविष्टि और सदस्यता शीघ्रता से की जा सकती है।  
 For each element $x_{i}$, एक सदस्यता क्वेरी जारी की जाती है।      
If $x_{i}$ is not a member of D ($x_{i}\notin D$)          

Add $x_{i}$ to D

         बढ़ोतरी c एक - एक करके, $c\leftarrow c+1$
     अन्यथा ($x_{i}\in D$) कुछ भी नहीं है।  

Output $n=c$.

जब तक अलग-अलग तत्वों की संख्या बहुत बड़ी न हो, D मुख्य मेमोरी में फिट हो जाता है और सटीक उत्तर प्राप्त किया जा सकता है। हालाँकि, यह दृष्टिकोण सीमित भंडारण के लिए या प्रत्येक तत्व के लिए की गई गणना के लिए स्केल नहीं करता है $x_{i}$ कम किया जाना चाहिए. ऐसे मामले में, कई स्ट्रीमिंग एल्गोरिदम प्रस्तावित किए गए हैं जो निश्चित संख्या में भंडारण इकाइयों का उपयोग करते हैं।

हाइपरलॉगलॉग एल्गोरिथम

Main article: HyperLogLog

स्ट्रीमिंग एल्गोरिदम

सीमित भंडारण बाधा को संभालने के लिए, स्ट्रीमिंग एल्गोरिदम तत्वों की विशिष्ट संख्या का गैर-सटीक अनुमान उत्पन्न करने के लिए यादृच्छिककरण का उपयोग करते हैं, $n$. अत्याधुनिक अनुमानक प्रत्येक तत्व को कार्यान्वित करते हैं $e_{j}$ हैश फ़ंक्शन का उपयोग करके निम्न-आयामी डेटा स्केच में, $h(e_{j})$. विभिन्न तकनीकों को उनके द्वारा संग्रहीत डेटा स्केच के अनुसार वर्गीकृत किया जा सकता है।

न्यूनतम/अधिकतम रेखाचित्र

न्यूनतम/अधिकतम रेखाचित्र केवल न्यूनतम/अधिकतम हैश किए गए मान संग्रहीत करें। ज्ञात न्यूनतम/अधिकतम स्केच अनुमानकों के उदाहरण: चेसिंग एट अल। अधिकतम रेखाचित्र प्रस्तुत करता है जो समस्या के लिए न्यूनतम-विचरण निष्पक्ष अनुमानक है। सतत अधिकतम रेखाचित्र अनुमानक अधिकतम संभावना अनुमानक है. व्यवहार में पसंद का अनुमानक हाइपरलॉगलॉग एल्गोरिदम है। ऐसे अनुमानकों के पीछे अंतर्ज्ञान यह है कि प्रत्येक स्केच में वांछित मात्रा के बारे में जानकारी होती है। उदाहरण के लिए, जब प्रत्येक तत्व $e_{j}$ एक समान यादृच्छिक चर के साथ जुड़ा हुआ है, $h(e_{j})\sim U(0,1)$, का अपेक्षित न्यूनतम मूल्य $h(e_{1}),h(e_{2}),\ldots ,h(e_{n})$ है $1/(n+1)$. हैश फ़ंक्शन इसकी गारंटी देता है $h(e_{j})$ के सभी स्वरूपों के लिए समान है $e_{j}$. इस प्रकार, डुप्लिकेट का अस्तित्व चरम क्रम के आँकड़ों के मूल्य को प्रभावित नहीं करता है।

न्यूनतम/अधिकतम रेखाचित्रों के अलावा अन्य अनुमान तकनीकें भी हैं। गिनती-विशिष्ट अनुमान पर पहला पेपर फ़्लैजोलेट-मार्टिन एल्गोरिथम, एक बिट पैटर्न स्केच का वर्णन करता है। इस मामले में, तत्वों को एक बिट वेक्टर में हैश किया गया है और स्केच सभी हैश किए गए मानों का तार्किक OR रखता है। इस समस्या के लिए पहला स्पर्शोन्मुख स्थान- और समय-इष्टतम एल्गोरिथ्म डैनियल केन (गणितज्ञ) द्वारा दिया गया था | डैनियल एम. केन, स्पष्टीकरण नेल्सन और डेविड पी. वुड्रूफ़।

नीचे-एम रेखाचित्र

बॉटम-एम रेखाचित्र न्यूनतम रेखाचित्रों का एक सामान्यीकरण है, जो बनाए रखता है $m$ न्यूनतम मान, कहाँ $m\geq 1$. कॉस्मा एट अल देखें।गिनती-विशिष्ट अनुमान एल्गोरिदम और मेटवॉली के सैद्धांतिक अवलोकन के लिए

तुलनात्मक सिमुलेशन परिणामों के साथ एक व्यावहारिक अवलोकन के लिए।

भारित गिनती-विशिष्ट समस्या

इसके भारित संस्करण में, प्रत्येक तत्व एक वजन के साथ जुड़ा हुआ है और लक्ष्य वजन के कुल योग का अनुमान लगाना है। औपचारिक रूप से,

उदाहरण: भारित तत्वों की एक धारा $x_{1},x_{2},\ldots ,x_{s}$ दोहराव और एक पूर्णांक के साथ $m$. होने देना $n$ अर्थात् भिन्न तत्वों की संख्या हो $n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|$, और इन तत्वों को रहने दें $\left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}$. अंत में, चलो $w_{j}$ का वजन हो $e_{j}$.

उद्देश्य: एक अनुमान खोजें ${\widehat {w}}$ का $w=\sum _{j=1}^{n}w_{j}$ केवल उपयोग कर रहे हैं $m$ भंडारण इकाइयाँ, कहाँ $m\ll n$.

भारित समस्या के उदाहरण का एक उदाहरण है: $a(3),b(4),a(3),c(2),d(3),b(4),d(3)$. इस उदाहरण के लिए, $e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d$, वजन हैं $w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3$ और $\sum {w_{j}}=12$.

एक एप्लिकेशन उदाहरण के रूप में, $x_{1},x_{2},\ldots ,x_{s}$ सर्वर द्वारा प्राप्त इंटरनेट प्रोटोकॉल पैकेट हो सकते हैं। प्रत्येक पैकेट किसी एक का है $n$ आईपी ​​प्रवाह $e_{1},e_{2},\ldots ,e_{n}$. भार $w_{j}$ प्रवाह द्वारा लगाया गया भार हो सकता है $e_{j}$ सर्वर पर. इस प्रकार, $\sum _{j=1}^{n}{w_{j}}$ यह उन सभी पैकेटों के प्रवाह द्वारा सर्वर पर लगाए गए कुल भार को दर्शाता है $x_{1},x_{2},\ldots ,x_{s}$ संबंधित होना।

भारित गिनती-विशिष्ट समस्या का समाधान

भारित समस्या के लिए किसी भी चरम क्रम सांख्यिकी अनुमानक (न्यूनतम/अधिकतम रेखाचित्र) को भारित समस्या के लिए एक अनुमानक के रूप में सामान्यीकृत किया जा सकता है . उदाहरण के लिए, कोहेन एट अल द्वारा प्रस्तावित भारित अनुमानक।जब भारित समस्या को हल करने के लिए निरंतर अधिकतम रेखाचित्र अनुमानक को बढ़ाया जाता है तो प्राप्त किया जा सकता है। विशेष रूप से, हाइपरलॉगलॉग एल्गोरिदमजटिल समस्या को हल करने के लिए इसे बढ़ाया जा सकता है। विस्तारित हाइपरलॉग एल्गोरिदम, भारित समस्या के लिए अन्य सभी ज्ञात एल्गोरिदम के बीच, सांख्यिकीय सटीकता और मेमोरी उपयोग के मामले में सबसे अच्छा प्रदर्शन प्रदान करता है।

यह भी देखें

• गिनती-मिनट स्केच
• स्ट्रीमिंग एल्गोरिदम
• अधिकतम संभाव्यता
• न्यूनतम-विचरण निष्पक्ष अनुमानक