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

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

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

उदाहरण: तत्वों की एक धारा $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\}$ हैं।

उद्देश्य: केवल $m$ संचयन इकाइयों का उपयोग करके $n$ का अनुमान ${\widehat {n}}$ खोजें, जहां $m\ll n$ है।

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

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

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

 Initialize a counter, c, to zero, .
 Initialize an efficient dictionary data structure, D, such as hash table or search tree in which insertion and membership can be performed quickly.  
 For each element , a membership query is issued. 
     If  is not a member of D ()
         Add  to D
         Increase c by one, 
     Otherwise () do nothing.
 Output .

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

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

Main article: हाइपरलॉगलॉग

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

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

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

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

ऐसे अनुमानकों के पीछे अंतर्ज्ञान यह है कि प्रत्येक स्केच में वांछित मात्रा के बारे में जानकारी होती है। उदाहरण के लिए, जब प्रत्येक तत्व $e_{j}$ एक समान RV, $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}$है।

उद्देश्य: केवल $m$ संचयन इकाइयों का उपयोग करके $w=\sum _{j=1}^{n}w_{j}$ का ${\widehat {w}}$ अनुमान लगाएं, जहां $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}$ संबंधित हैं।

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

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

यह भी देखें

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