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

Revision as of 15:24, 8 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>{{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> (जिसे व्यावहारिक गणित में कार्डिनैलिटी अनुमान समस्या के रूप में भी जाना जाता है) दोहराए गए तत्वों के साथ डेटा स्ट्रीम में अलग-अलग तत्वों की संख्या खोजने की समस्या है। यह अनेक अनुप्रयोगों में एक सुविख्यात समस्या है। तत्व राउटर से गुजरने वाले पैकेट के आईपी एड्रेस, वेब साइट पर अद्वितीय विज़िटर, बड़े डेटाबेस में तत्व, डीएनए अनुक्रम में रूपांकनों, या आरएफआईडी/सेंसर नेटवर्क के तत्वों का प्रतिनिधित्व कर सकते हैं।
@@ Line 36: / Line 36: @@
 ऐसे अनुमानकों के पीछे अंतर्ज्ञान यह है कि प्रत्येक स्केच में वांछित मात्रा के बारे में जानकारी होती है। उदाहरण के लिए, जब प्रत्येक तत्व <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> न्यूनतम रेखाचित्रों का एक सामान्यीकरण है, जो <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>
-==भारित गिनती-विशिष्ट समस्या==
+==भारित गणना-विशिष्ट समस्या==
 इसके भारित संस्करण में, प्रत्येक तत्व एक वजन के साथ जुड़ा हुआ है और लक्ष्य वजन के कुल योग का अनुमान लगाना है।
@@ Line 57: / Line 57: @@
                                                                             </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 /> को भारित समस्या को हल करने के लिए बढ़ाया जा सकता है। विस्तारित हाइपरलॉग एल्गोरिदम, भारित समस्या के लिए अन्य सभी ज्ञात एल्गोरिदम के बीच, सांख्यिकीय स्पष्टता और मेमोरी उपयोग के स्थिति में सबसे अच्छा प्रदर्शन प्रदान करता है।
 ==यह भी देखें==
-* गिनती-मिनट स्केच
+* गणना-मिनट स्केच
 * स्ट्रीमिंग एल्गोरिदम
 * अधिकतम संभाव्यता

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 15:24, 8 August 2023

Contents

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 15:24, 8 August 2023

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories