गणना-विशिष्ट समस्या: Difference between revisions

Revision as of 20:26, 7 August 2023

कंप्यूटर विज्ञान में, गिनती-विशिष्ट समस्या^[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\}

हैं।

उद्देश्य: केवल

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}$ के लिए की गई गणना को कम किया जाना चाहिए। ऐसे स्थिति में, अनेक स्ट्रीमिंग एल्गोरिदम प्रस्तावित किए गए हैं जो निश्चित संख्या में संचयन इकाइयों का उपयोग करते हैं।

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

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

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

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

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

ऐसे अनुमानकों के पीछे अंतर्ज्ञान यह है कि प्रत्येक स्केच में वांछित मात्रा के बारे में जानकारी होती है। उदाहरण के लिए, जब प्रत्येक तत्व $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}$ की सभी अभिव्यक्तियों के लिए समान है। इस प्रकार, डुप्लिकेट का अस्तित्व चरम क्रम के आँकड़ों के मान को प्रभावित नहीं करता है।

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

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

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

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

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

औपचारिक रूप से,

उदाहरण: भारित तत्वों की एक धारा

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}$ संबंधित हैं।

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

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

यह भी देखें

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

संदर्भ

↑ Ullman, Jeff; Rajaraman, Anand; Leskovec, Jure. "खनन डेटा धाराएँ" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
↑ ^2.0 ^2.1 Cosma, Ioana A.; Clifford, Peter (2011). "संभाव्य गणना एल्गोरिदम का एक सांख्यिकीय विश्लेषण". Scandinavian Journal of Statistics. arXiv:0801.3552.
↑ Giroire, Frederic; Fusy, Eric (2007). 2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). pp. 223–231. CiteSeerX 10.1.1.214.270. doi:10.1137/1.9781611972979.9. ISBN 978-1-61197-297-9.
↑ Chassaing, Philippe; Gerin, Lucas (2006). "बड़े डेटा सेट की प्रमुखता का कुशल अनुमान". Proceedings of the 4th Colloquium on Mathematics and Computer Science. arXiv:math/0701347. Bibcode:2007math......1347C.
↑ ^5.0 ^5.1 Cohen, Edith (1997). "ट्रांजिटिव क्लोजर और रीचैबिलिटी के अनुप्रयोगों के साथ आकार-आकलन ढांचा". J. Comput. Syst. Sci. 55 (3): 441–453. doi:10.1006/jcss.1997.1534.
↑ ^6.0 ^6.1 Flajolet, Philippe; Fusy, Eric; Gandouet, Olivier; Meunier, Frederic (2007). "HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm" (PDF). Analysis of Algorithms.
↑ Flajolet, Philippe; Martin, G. Nigel (1985). "डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम" (PDF). J. Comput. Syst. Sci. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8.
↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "विशिष्ट तत्व समस्या के लिए एक इष्टतम एल्गोरिदम". Proceedings of the 29th Annual ACM Symposium on Principles of Database Systems (PODS).
↑ Cohen, Edith; Kaplan, Haim (2008). "नीचे के रेखाचित्रों का उपयोग करके सख्त अनुमान" (PDF). PVLDB.
↑ Metwally, Ahmed; Agrawal, Divyakant; Abbadi, Amr El (2008), Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic, Proceedings of the 11th international conference on Extending Database Technology: Advances in Database Technology, pp. 618–629, CiteSeerX 10.1.1.377.4771
↑ Cohen, Reuven; Katzir, Liran; Yehezkel, Aviv (2014). "योग एकत्रीकरण के लिए कार्डिनैलिटी अनुमानकों को सामान्य बनाने के लिए एक एकीकृत योजना". Information Processing Letters. 115 (2): 336–342. doi:10.1016/j.ipl.2014.10.009.

[1] Ullman, Jeff; Rajaraman, Anand; Leskovec, Jure. "खनन डेटा धाराएँ" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

[cosma2011-2] 2.0 ^2.1 Cosma, Ioana A.; Clifford, Peter (2011). "संभाव्य गणना एल्गोरिदम का एक सांख्यिकीय विश्लेषण". Scandinavian Journal of Statistics. arXiv:0801.3552.

[3] Giroire, Frederic; Fusy, Eric (2007). 2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). pp. 223–231. CiteSeerX 10.1.1.214.270. doi:10.1137/1.9781611972979.9. ISBN 978-1-61197-297-9.

[4] Chassaing, Philippe; Gerin, Lucas (2006). "बड़े डेटा सेट की प्रमुखता का कुशल अनुमान". Proceedings of the 4th Colloquium on Mathematics and Computer Science. arXiv:math/0701347. Bibcode:2007math......1347C.

[edithCohen-5] 5.0 ^5.1 Cohen, Edith (1997). "ट्रांजिटिव क्लोजर और रीचैबिलिटी के अनुप्रयोगों के साथ आकार-आकलन ढांचा". J. Comput. Syst. Sci. 55 (3): 441–453. doi:10.1006/jcss.1997.1534.

[hyperloglog-6] 6.0 ^6.1 Flajolet, Philippe; Fusy, Eric; Gandouet, Olivier; Meunier, Frederic (2007). "HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm" (PDF). Analysis of Algorithms.

[7] Flajolet, Philippe; Martin, G. Nigel (1985). "डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम" (PDF). J. Comput. Syst. Sci. 31 (2): 182–209. doi:10.1016/0022-0000(85)90041-8.

[optimalf0-8] Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "विशिष्ट तत्व समस्या के लिए एक इष्टतम एल्गोरिदम". Proceedings of the 29th Annual ACM Symposium on Principles of Database Systems (PODS).

[9] Cohen, Edith; Kaplan, Haim (2008). "नीचे के रेखाचित्रों का उपयोग करके सख्त अनुमान" (PDF). PVLDB.

[10] Metwally, Ahmed; Agrawal, Divyakant; Abbadi, Amr El (2008), Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic, Proceedings of the 11th international conference on Extending Database Technology: Advances in Database Technology, pp. 618–629, CiteSeerX 10.1.1.377.4771

[11] Cohen, Reuven; Katzir, Liran; Yehezkel, Aviv (2014). "योग एकत्रीकरण के लिए कार्डिनैलिटी अनुमानकों को सामान्य बनाने के लिए एक एकीकृत योजना". Information Processing Letters. 115 (2): 336–342. doi:10.1016/j.ipl.2014.10.009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
-कंप्यूटर विज्ञान में, गिनती-विशिष्ट समस्या<ref>{{cite journal | last1=Ullman | first1=Jeff |author1-link=Jeffrey Ullman| last2 = Rajaraman | first2 = Anand | last3=Leskovec | first3=Jure |author3-link=Jure Leskovec| title=खनन डेटा धाराएँ| url=http://infolab.stanford.edu/~ullman/mmds/ch4.pdf}}
-</ref>
-(अनुप्रयुक्त गणित में कार्डिनैलिटी अनुमान समस्या के रूप में भी जाना जाता है) दोहराए गए तत्वों के साथ डेटा स्ट्रीम में अलग-अलग तत्वों की संख्या खोजने की समस्या है।
+कंप्यूटर विज्ञान में, '''गिनती-विशिष्ट समस्या'''<ref>{{cite journal | last1=Ullman | first1=Jeff |author1-link=Jeffrey Ullman| last2 = Rajaraman | first2 = Anand | last3=Leskovec | first3=Jure |author3-link=Jure Leskovec| title=खनन डेटा धाराएँ| url=http://infolab.stanford.edu/~ullman/mmds/ch4.pdf}}
-यह अनेक अनुप्रयोगों में एक सुविख्यात समस्या है। तत्व [[राउटर (कंप्यूटिंग)]] से गुजरने वाले पैकेट के आईपी पते, किसी वेब साइट पर अद्वितीय विज़िटर, बड़े डेटाबेस में तत्व, [[डीएनए]] अनुक्रम में रूपांकनों, या [[आरएफआईडी]]/[[सेंसर नेटवर्क]] के तत्वों का प्रतिनिधित्व कर सकते हैं।
+</ref> (जिसे व्यावहारिक गणित में कार्डिनैलिटी अनुमान समस्या के रूप में भी जाना जाता है) दोहराए गए तत्वों के साथ डेटा स्ट्रीम में अलग-अलग तत्वों की संख्या खोजने की समस्या है। यह अनेक अनुप्रयोगों में एक सुविख्यात समस्या है। तत्व राउटर से गुजरने वाले पैकेट के आईपी एड्रेस, वेब साइट पर अद्वितीय विज़िटर, बड़े डेटाबेस में तत्व, डीएनए अनुक्रम में रूपांकनों, या आरएफआईडी/सेंसर नेटवर्क के तत्वों का प्रतिनिधित्व कर सकते हैं।
 ==औपचारिक परिभाषा==
-: उदाहरण: तत्वों की एक धारा <math> x_1,x_2,\ldots,x_s </math> दोहराव और एक पूर्णांक के साथ <math> m </math>. होने देना <math> n </math> अर्थात् भिन्न तत्वों की संख्या हो <math> n = |\left\{ {x_1,x_2,\ldots,x_s}\right\}| </math>, और इन तत्वों को रहने दें <math> \left\{ {e_1,e_2,\ldots,e_n}\right\} </math>.
+:उदाहरण: तत्वों की एक धारा <math> x_1,x_2,\ldots,x_s </math> दोहराव के साथ, और एक पूर्णांक <math> m </math> मान लीजिए <math> n </math> अलग-अलग तत्वों की संख्या है, अर्थात् <math> n = |\left\{ {x_1,x_2,\ldots,x_s}\right\}| </math> और मान लीजिए कि ये तत्व <math> \left\{ {e_1,e_2,\ldots,e_n}\right\} </math> हैं।
-: उद्देश्य: एक अनुमान खोजें <math> \widehat{n} </math> का <math> n </math> केवल उपयोग कर रहे हैं <math> m </math> भंडारण इकाइयाँ, कहाँ <math> m \ll n </math>.
+:उद्देश्य: केवल <math> m </math> संचयन इकाइयों का उपयोग करके <math> n </math> का अनुमान <math> \widehat{n} </math> खोजें, जहां <math> m \ll n </math> है।
-कार्डिनैलिटी अनुमान समस्या के उदाहरण का एक उदाहरण स्ट्रीम है: <math> a,b,a,c,d,b,d </math>. इस उदाहरण के लिए, <math> n = |\left\{ {a,b,c,d}\right\}| = 4 </math>.
+कार्डिनैलिटी अनुमान समस्या के उदाहरण का एक उदाहरण स्ट्रीम है: <math> a,b,a,c,d,b,d </math>. इस उदाहरण के लिए, <math> n = |\left\{ {a,b,c,d}\right\}| = 4 </math>. है
 ==अनुचित समाधान==
 समस्या का सरल समाधान इस प्रकार है:
-  एक काउंटर प्रारंभ करें, {{mvar|c}}, शून्य तक, {{nowrap|<math> c \leftarrow 0 </math>.}}
-  एक कुशल शब्दकोश डेटा संरचना प्रारंभ करें, {{mvar|D}}, जैसे हैश टेबल या सर्च ट्री जिसमें प्रविष्टि और सदस्यता शीघ्रता से की जा सकती है।
-  {{nowrap|For each element <math> x_i </math>}}, एक सदस्यता क्वेरी जारी की जाती है।
- {{nowrap|If <math> x_i </math> is not a member of {{mvar|D}}}} {{nowrap|(<math> x_i \notin D </math>)}}
-{{nowrap|Add <math> x_i </math> to {{mvar|D}}}}
-          बढ़ोतरी {{mvar|c}} एक - एक करके, {{nowrap|<math> c \leftarrow c + 1</math>}}
-      अन्यथा {{nowrap|(<math> x_i \in D </math>)}} कुछ भी नहीं है।
-{{nowrap|Output <math> n = c </math>.}}
-जब तक अलग-अलग तत्वों की संख्या बहुत बड़ी न हो, {{mvar|D}} मुख्य मेमोरी में फिट हो जाता है और सटीक उत्तर प्राप्त किया जा सकता है।
+  Initialize a counter, c, to zero, .
-हालाँकि, यह दृष्टिकोण सीमित भंडारण के लिए या प्रत्येक तत्व के लिए की गई गणना के लिए स्केल नहीं करता है <math> x_i </math> कम किया जाना चाहिए. ऐसे मामले में, कई [[स्ट्रीमिंग एल्गोरिदम]] प्रस्तावित किए गए हैं जो निश्चित संख्या में भंडारण इकाइयों का उपयोग करते हैं।
+  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 .
+जब तक अलग-अलग तत्वों की संख्या बहुत बड़ी न हो, {{mvar|D}} मुख्य मेमोरी में फिट हो जाता है और एक स्पष्ट उत्तर प्राप्त किया जा सकता है। चूँकि यह दृष्टिकोण सीमित संचयन के लिए स्केल नहीं करता है, या यदि प्रत्येक तत्व <math> x_i </math> के लिए की गई गणना को कम किया जाना चाहिए। ऐसे स्थिति में, अनेक स्ट्रीमिंग एल्गोरिदम प्रस्तावित किए गए हैं जो निश्चित संख्या में संचयन इकाइयों का उपयोग करते हैं।
 ==हाइपरलॉगलॉग एल्गोरिथम==
-{{main|HyperLogLog}}
+{{main|हाइपरलॉगलॉग}}
 ==[[स्ट्रीमिंग एल्गोरिदम]]==
-सीमित भंडारण बाधा को संभालने के लिए, स्ट्रीमिंग एल्गोरिदम तत्वों की विशिष्ट संख्या का गैर-सटीक अनुमान उत्पन्न करने के लिए यादृच्छिककरण का उपयोग करते हैं, <math> n</math>.
+सीमित संचयन बाधा को संभालने के लिए, स्ट्रीमिंग एल्गोरिदम तत्वों की विशिष्ट संख्या का गैर-स्पष्ट अनुमान उत्पन्न करने के लिए यादृच्छिककरण का उपयोग करते हैं, जिसमे <math> n</math> अत्याधुनिक अनुमानकों ने हैश फलन , <math> h(e_j) </math> का उपयोग करके प्रत्येक तत्व <math> e_j </math> को निम्न-आयामी डेटा स्केच में हैश किया है। विभिन्न तकनीकों को उनके द्वारा संग्रहीत डेटा स्केच के अनुसार वर्गीकृत किया जा सकता है।
-अत्याधुनिक अनुमानक प्रत्येक तत्व को कार्यान्वित करते हैं <math> e_j </math> हैश फ़ंक्शन का उपयोग करके निम्न-आयामी डेटा स्केच में, <math> h(e_j) </math>.
-विभिन्न तकनीकों को उनके द्वारा संग्रहीत डेटा स्केच के अनुसार वर्गीकृत किया जा सकता है।
 === न्यूनतम/अधिकतम रेखाचित्र ===
-न्यूनतम/अधिकतम रेखाचित्र<ref name=cosma2011>{{cite journal | last1=Cosma | first1=Ioana A. | last2 = Clifford | first2 = Peter | year=2011 | title=संभाव्य गणना एल्गोरिदम का एक सांख्यिकीय विश्लेषण| journal=Scandinavian Journal of Statistics| arxiv=0801.3552 }} </ref><ref>{{cite book | last1=Giroire | first1=Frederic | title=2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) | pages=223–231 | last2 = Fusy | first2 = Eric | year=2007 |citeseerx=10.1.1.214.270 |doi=10.1137/1.9781611972979.9| isbn=978-1-61197-297-9 }} </ref> केवल न्यूनतम/अधिकतम हैश किए गए मान संग्रहीत करें। ज्ञात न्यूनतम/अधिकतम स्केच अनुमानकों के उदाहरण: चेसिंग एट अल।<ref>{{cite journal | last1=Chassaing | first1=Philippe | last2=Gerin | first2=Lucas | year=2006| title=बड़े डेटा सेट की प्रमुखता का कुशल अनुमान| journal=Proceedings of the 4th Colloquium on Mathematics and Computer Science| bibcode=2007math......1347C | arxiv=math/0701347 }} </ref> अधिकतम रेखाचित्र प्रस्तुत करता है जो समस्या के लिए [[न्यूनतम-विचरण निष्पक्ष अनुमानक]] है। सतत अधिकतम रेखाचित्र अनुमानक<ref name=edithCohen>{{cite journal | last1=Cohen | first1=Edith |authorlink=Edith Cohen| year=1997| title=ट्रांजिटिव क्लोजर और रीचैबिलिटी के अनुप्रयोगों के साथ आकार-आकलन ढांचा| journal=J. Comput. Syst. Sci.| volume=55 | issue=3 | pages=441–453 | doi=10.1006/jcss.1997.1534 | doi-access=free }} </ref> अधिकतम संभावना अनुमानक है. व्यवहार में पसंद का अनुमानक [[हाइपरलॉगलॉग]] एल्गोरिदम है।<ref name=hyperloglog>{{cite journal | last1=Flajolet | first1=Philippe|author1-link=Philippe Flajolet | last2 = Fusy | first2 = Eric | last3=Gandouet | first3=Olivier | last4=Meunier | first4=Frederic | title=HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm | journal=Analysis of Algorithms |year=2007|url=https://hal.archives-ouvertes.fr/docs/00/40/61/66/PDF/FlFuGaMe07.pdf}} </ref>
+न्यूनतम/अधिकतम रेखाचित्र<ref name=cosma2011>{{cite journal | last1=Cosma | first1=Ioana A. | last2 = Clifford | first2 = Peter | year=2011 | title=संभाव्य गणना एल्गोरिदम का एक सांख्यिकीय विश्लेषण| journal=Scandinavian Journal of Statistics| arxiv=0801.3552 }} </ref><ref>{{cite book | last1=Giroire | first1=Frederic | title=2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) | pages=223–231 | last2 = Fusy | first2 = Eric | year=2007 |citeseerx=10.1.1.214.270 |doi=10.1137/1.9781611972979.9| isbn=978-1-61197-297-9 }} </ref> केवल न्यूनतम/अधिकतम हैश किए गए मान संग्रहीत करें। ज्ञात न्यूनतम/अधिकतम स्केच अनुमानकों के उदाहरण: चेसिंग एट अल<ref>{{cite journal | last1=Chassaing | first1=Philippe | last2=Gerin | first2=Lucas | year=2006| title=बड़े डेटा सेट की प्रमुखता का कुशल अनुमान| journal=Proceedings of the 4th Colloquium on Mathematics and Computer Science| bibcode=2007math......1347C | arxiv=math/0701347 }} </ref> अधिकतम रेखाचित्र प्रस्तुत करता है जो समस्या के लिए [[न्यूनतम-विचरण निष्पक्ष अनुमानक]] है। सतत अधिकतम रेखाचित्र अनुमानक<ref name=edithCohen>{{cite journal | last1=Cohen | first1=Edith |authorlink=Edith Cohen| year=1997| title=ट्रांजिटिव क्लोजर और रीचैबिलिटी के अनुप्रयोगों के साथ आकार-आकलन ढांचा| journal=J. Comput. Syst. Sci.| volume=55 | issue=3 | pages=441–453 | doi=10.1006/jcss.1997.1534 | doi-access=free }} </ref> अधिकतम संभावना अनुमानक है. वास्तव में इच्छित का अनुमानक [[हाइपरलॉगलॉग]] एल्गोरिदम है।<ref name=hyperloglog>{{cite journal | last1=Flajolet | first1=Philippe|author1-link=Philippe Flajolet | last2 = Fusy | first2 = Eric | last3=Gandouet | first3=Olivier | last4=Meunier | first4=Frederic | title=HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm | journal=Analysis of Algorithms |year=2007|url=https://hal.archives-ouvertes.fr/docs/00/40/61/66/PDF/FlFuGaMe07.pdf}} </ref>
-ऐसे अनुमानकों के पीछे अंतर्ज्ञान यह है कि प्रत्येक स्केच में वांछित मात्रा के बारे में जानकारी होती है। उदाहरण के लिए, जब प्रत्येक तत्व <math> e_j </math> एक समान यादृच्छिक चर के साथ जुड़ा हुआ है, <math> h(e_j) \sim U(0,1) </math>, का अपेक्षित न्यूनतम मूल्य <math> h(e_1),h(e_2), \ldots, h(e_n) </math> है <math> 1/(n+1) </math>. हैश फ़ंक्शन इसकी गारंटी देता है <math> h(e_j) </math> के सभी स्वरूपों के लिए समान है <math> e_j </math>. इस प्रकार, डुप्लिकेट का अस्तित्व चरम क्रम के आँकड़ों के मूल्य को प्रभावित नहीं करता है।
+ऐसे अनुमानकों के पीछे अंतर्ज्ञान यह है कि प्रत्येक स्केच में वांछित मात्रा के बारे में जानकारी होती है। उदाहरण के लिए, जब प्रत्येक तत्व <math> e_j </math> एक समान RV, <math> h(e_j) \sim U(0,1) </math> से जुड़ा होता है, तो <math> h(e_1),h(e_2), \ldots, h(e_n) </math> का अपेक्षित न्यूनतम मान <math> 1/(n+1) </math> होता है। हैश फलन  आश्वासन देता है कि <math> h(e_j) </math>, <math> e_j </math> की सभी अभिव्यक्तियों के लिए समान है। इस प्रकार, डुप्लिकेट का अस्तित्व चरम क्रम के आँकड़ों के मान को प्रभावित नहीं करता है।
-न्यूनतम/अधिकतम रेखाचित्रों के अलावा अन्य अनुमान तकनीकें भी हैं। गिनती-विशिष्ट अनुमान पर पहला पेपर<ref>{{cite journal | last1=Flajolet | first1=Philippe|author1-link=Philippe Flajolet | last2 = Martin | first2 = G. Nigel | year=1985 | title=डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम| journal=J. Comput. Syst. Sci. | volume=31| issue=2| pages=182–209| doi=10.1016/0022-0000(85)90041-8| url=https://hal.inria.fr/inria-00076244/file/RR-0313.pdf}} </ref> फ़्लैजोलेट-मार्टिन एल्गोरिथम, एक बिट पैटर्न स्केच का वर्णन करता है। इस मामले में, तत्वों को एक बिट वेक्टर में हैश किया गया है और स्केच सभी हैश किए गए मानों का तार्किक OR रखता है। इस समस्या के लिए पहला स्पर्शोन्मुख स्थान- और समय-इष्टतम एल्गोरिथ्म डैनियल केन (गणितज्ञ) द्वारा दिया गया था | डैनियल एम. केन, [[ स्पष्टीकरण नेल्सन ]] और डेविड पी. वुड्रूफ़।<ref name=optimalf0>{{cite journal | last1=Kane | first1=Daniel M. | last2 = Nelson | first2 = Jelani | last3=Woodruff | first3=David P. | year=2010 | authorlink1=Daniel_Kane_(mathematician) | authorlink2=Jelani_Nelson | title=विशिष्ट तत्व समस्या के लिए एक इष्टतम एल्गोरिदम| journal=Proceedings of the 29th Annual ACM Symposium on Principles of Database Systems (PODS)|url=https://dash.harvard.edu/bitstream/handle/1/13820438/f0.pdf;sequence=1}} </ref>
+न्यूनतम/अधिकतम रेखाचित्रों के अतिरिक्त अन्य अनुमान तकनीकें भी हैं। गिनती-विशिष्ट अनुमान पर पहला पेपर<ref>{{cite journal | last1=Flajolet | first1=Philippe|author1-link=Philippe Flajolet | last2 = Martin | first2 = G. Nigel | year=1985 | title=डेटा बेस अनुप्रयोगों के लिए संभाव्य गणना एल्गोरिदम| journal=J. Comput. Syst. Sci. | volume=31| issue=2| pages=182–209| doi=10.1016/0022-0000(85)90041-8| url=https://hal.inria.fr/inria-00076244/file/RR-0313.pdf}} </ref> फ़्लैजोलेट-मार्टिन एल्गोरिदम, एक बिट पैटर्न स्केच का वर्णन करता है। इस स्थिति में, तत्वों को एक बिट सदिश में हैश किया गया है और स्केच सभी हैश किए गए मानों का तार्किक OR रखता है। इस समस्या के लिए पहला स्पर्शोन्मुख स्थान- और समय-इष्टतम एल्गोरिदम डैनियल एम. केन, जेलानी नेल्सन और डेविड पी. वुड्रूफ़ द्वारा दिया गया था।<ref name="optimalf0">{{cite journal | last1=Kane | first1=Daniel M. | last2 = Nelson | first2 = Jelani | last3=Woodruff | first3=David P. | year=2010 | authorlink1=Daniel_Kane_(mathematician) | authorlink2=Jelani_Nelson | title=विशिष्ट तत्व समस्या के लिए एक इष्टतम एल्गोरिदम| journal=Proceedings of the 29th Annual ACM Symposium on Principles of Database Systems (PODS)|url=https://dash.harvard.edu/bitstream/handle/1/13820438/f0.pdf;sequence=1}} </ref>
 ===नीचे-एम रेखाचित्र===
-बॉटम-एम रेखाचित्र
+बॉटम-एम रेखाचित्र <ref>{{cite journal | last1=Cohen | first1=Edith|author1-link=Edith Cohen | last2 = Kaplan | first2 = Haim | year=2008 | title=नीचे के रेखाचित्रों का उपयोग करके सख्त अनुमान| journal=PVLDB | url=http://www.vldb.org/pvldb/1/1453884.pdf}}
-<ref>{{cite journal | last1=Cohen | first1=Edith|author1-link=Edith Cohen | last2 = Kaplan | first2 = Haim | year=2008 | title=नीचे के रेखाचित्रों का उपयोग करके सख्त अनुमान| journal=PVLDB | url=http://www.vldb.org/pvldb/1/1453884.pdf}}
+</ref> न्यूनतम रेखाचित्रों का एक सामान्यीकरण है, जो <math> m </math> न्यूनतम मान बनाए रखता है, जहां <math> m \geq 1 </math> कॉस्मा एट अल देखें।<ref name=cosma2011 /> गिनती-विशिष्ट अनुमान एल्गोरिदम के सैद्धांतिक अवलोकन के लिए, और तुलनात्मक सिमुलेशन परिणामों के साथ व्यावहारिक अवलोकन के लिए मेटवॉली है <ref>{{Citation | last1=Metwally | first1=Ahmed | last2=Agrawal | first2=Divyakant | last3=Abbadi | first3= Amr El | year=2008 | title=Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic | series=Proceedings of the 11th international conference on Extending Database Technology: Advances in Database Technology | pages=618–629 | citeseerx=10.1.1.377.4771 }}
-</ref> न्यूनतम रेखाचित्रों का एक सामान्यीकरण है, जो बनाए रखता है <math> m </math> न्यूनतम मान, कहाँ <math> m \geq 1 </math>.
-कॉस्मा एट अल देखें।<ref name=cosma2011 />गिनती-विशिष्ट अनुमान एल्गोरिदम और मेटवॉली के सैद्धांतिक अवलोकन के लिए
- <ref>{{Citation | last1=Metwally | first1=Ahmed | last2=Agrawal | first2=Divyakant | last3=Abbadi | first3= Amr El | year=2008 | title=Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic | series=Proceedings of the 11th international conference on Extending Database Technology: Advances in Database Technology | pages=618–629 | citeseerx=10.1.1.377.4771 }}
 </ref>
-तुलनात्मक सिमुलेशन परिणामों के साथ एक व्यावहारिक अवलोकन के लिए।
 ==भारित गिनती-विशिष्ट समस्या==
 इसके भारित संस्करण में, प्रत्येक तत्व एक वजन के साथ जुड़ा हुआ है और लक्ष्य वजन के कुल योग का अनुमान लगाना है।
 औपचारिक रूप से,
-: उदाहरण: भारित तत्वों की एक धारा <math> x_1,x_2,\ldots,x_s </math> दोहराव और एक पूर्णांक के साथ <math> m </math>. होने देना <math> n </math> अर्थात् भिन्न तत्वों की संख्या हो <math> n = |\left\{ {x_1,x_2,\ldots,x_s}\right\}| </math>, और इन तत्वों को रहने दें <math> \left\{ {e_1,e_2,\ldots,e_n}\right\} </math>. अंत में, चलो <math> w_j </math> का वजन हो <math> e_j </math>.
+:उदाहरण: भारित तत्वों की एक धारा <math> x_1,x_2,\ldots,x_s </math> दोहराव के साथ, और एक पूर्णांक <math> m </math> मान लीजिए कि <math> n </math> अलग-अलग तत्वों की संख्या है, अर्थात् <math> n = |\left\{ {x_1,x_2,\ldots,x_s}\right\}| </math>, और इन तत्वों को <math> \left\{ {e_1,e_2,\ldots,e_n}\right\} </math> होने दें  अंततः, मान लीजिए कि <math> w_j </math> का भार <math> e_j </math>है।
-: उद्देश्य: एक अनुमान खोजें <math> \widehat{w} </math> का <math> w = \sum_{j=1}^{n}w_j </math> केवल उपयोग कर रहे हैं <math> m </math> भंडारण इकाइयाँ, कहाँ <math> m \ll n </math>.
+:उद्देश्य: केवल <math> m </math> संचयन  इकाइयों का उपयोग करके <math> w = \sum_{j=1}^{n}w_j </math> का <math> \widehat{w} </math> अनुमान लगाएं, जहां <math> m \ll n </math>.
-भारित समस्या के उदाहरण का एक उदाहरण है: <math> a(3),b(4),a(3),c(2),d(3),b(4),d(3) </math>. इस उदाहरण के लिए, <math> e_1=a, e_2=b, e_3=c, e_4=d </math>, वजन हैं <math> w_1=3, w_2=4, w_3=2, w_4=3 </math> और <math> \sum{w_j}=12 </math>.
+भारित समस्या के उदाहरण का एक उदाहरण है: <math> a(3),b(4),a(3),c(2),d(3),b(4),d(3) </math> इस उदाहरण के लिए, <math> e_1=a, e_2=b, e_3=c, e_4=d </math>, वज़न <math> w_1=3, w_2=4, w_3=2, w_4=3 </math> और <math> \sum{w_j}=12 </math> है
-एक एप्लिकेशन उदाहरण के रूप में, <math> x_1,x_2,\ldots,x_s </math> सर्वर द्वारा प्राप्त [[इंटरनेट प्रोटोकॉल]] पैकेट हो सकते हैं। प्रत्येक पैकेट किसी एक का है <math> n </math> आईपी प्रवाह <math> e_1,e_2,\ldots,e_n </math>. भार <math> w_j </math> प्रवाह द्वारा लगाया गया भार हो सकता है <math> e_j </math> सर्वर पर. इस प्रकार, <math> \sum_{j=1}^{n}{w_j} </math> यह उन सभी पैकेटों के प्रवाह द्वारा सर्वर पर लगाए गए कुल भार को दर्शाता है <math> x_1,x_2,\ldots,x_s </math> संबंधित होना।
+एप्लिकेशन उदाहरण के रूप में, <math> x_1,x_2,\ldots,x_s </math> एक सर्वर द्वारा प्राप्त आईपी पैकेट हो सकते हैं। प्रत्येक पैकेट <math> n </math> आईपी प्रवाह <math> e_1,e_2,\ldots,e_n </math> में से एक से संबंधित है। भार <math> w_j </math> सर्वर पर प्रवाह <math> e_j </math> द्वारा लगाया गया भार हो सकता है। इस प्रकार, <math> \sum_{j=1}^{n}{w_j} </math> सभी प्रवाहों द्वारा सर्वर पर लगाए गए कुल भार का प्रतिनिधित्व करता है जिसमें <math> x_1,x_2,\ldots,x_s </math> संबंधित हैं।
 ==भारित गिनती-विशिष्ट समस्या का समाधान==
-भारित समस्या के लिए किसी भी चरम क्रम सांख्यिकी अनुमानक (न्यूनतम/अधिकतम रेखाचित्र) को भारित समस्या के लिए एक अनुमानक के रूप में सामान्यीकृत किया जा सकता है
+भारित समस्या के लिए किसी भी चरम क्रम सांख्यिकी अनुमानक (न्यूनतम/अधिकतम रेखाचित्र) को भारित समस्या के लिए एक अनुमानक के रूप में सामान्यीकृत किया जा सकता है।<ref>{{cite journal | last1=Cohen |author1-link=Edith Cohen| first1=Reuven | last2 = Katzir | first2 = Liran | last3=Yehezkel | first3=Aviv | year=2014| title=योग एकत्रीकरण के लिए कार्डिनैलिटी अनुमानकों को सामान्य बनाने के लिए एक एकीकृत योजना| journal=Information Processing Letters|doi=10.1016/j.ipl.2014.10.009 | volume=115 |issue=2| pages=336–342}}</ref> उदाहरण के लिए, कोहेन एट अल द्वारा प्रस्तावित भारित अनुमानक।<ref name=edithCohen /> जब भारित समस्या को हल करने के लिए निरंतर अधिकतम रेखाचित्र अनुमानक को बढ़ाया जाता है तो प्राप्त किया जा सकता है। विशेष रूप से, हाइपरलॉगलॉग एल्गोरिदम<ref name=hyperloglog /> को भारित समस्या को हल करने के लिए बढ़ाया जा सकता है। विस्तारित हाइपरलॉग एल्गोरिदम, भारित समस्या के लिए अन्य सभी ज्ञात एल्गोरिदम के बीच, सांख्यिकीय स्पष्टता और मेमोरी उपयोग के स्थिति में सबसे अच्छा प्रदर्शन प्रदान करता है।
-.<ref>{{cite journal | last1=Cohen |author1-link=Edith Cohen| first1=Reuven | last2 = Katzir | first2 = Liran | last3=Yehezkel | first3=Aviv | year=2014| title=योग एकत्रीकरण के लिए कार्डिनैलिटी अनुमानकों को सामान्य बनाने के लिए एक एकीकृत योजना| journal=Information Processing Letters|doi=10.1016/j.ipl.2014.10.009 | volume=115 |issue=2| pages=336–342}}</ref>
-उदाहरण के लिए, कोहेन एट अल द्वारा प्रस्तावित भारित अनुमानक।<ref name=edithCohen />जब भारित समस्या को हल करने के लिए निरंतर अधिकतम रेखाचित्र अनुमानक को बढ़ाया जाता है तो प्राप्त किया जा सकता है।
-विशेष रूप से, हाइपरलॉगलॉग एल्गोरिदम<ref name=hyperloglog />जटिल समस्या को हल करने के लिए इसे बढ़ाया जा सकता है। विस्तारित हाइपरलॉग एल्गोरिदम, भारित समस्या के लिए अन्य सभी ज्ञात एल्गोरिदम के बीच, सांख्यिकीय सटीकता और मेमोरी उपयोग के मामले में सबसे अच्छा प्रदर्शन प्रदान करता है।
 ==यह भी देखें==

Anonymous

Search

गणना-विशिष्ट समस्या: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:26, 7 August 2023

Contents

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

गणना-विशिष्ट समस्या: Difference between revisions

Revision as of 20:26, 7 August 2023

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories