</ref> 1978 की शुरुआत में, साथ ही 1982/83 में [[फिलिप फ्लेजोलेट]] और जी. निगेल मार्टिन,<ref name=":0"/>स्ट्रीमिंग एल्गोरिदम के क्षेत्र को पहली बार 1996 में [[ सावधान अलोन ]], [[योसी मतियास]] और [[मारियो सजेगेडी]] द्वारा एक पेपर में औपचारिक और लोकप्रिय बनाया गया था।<ref name=":1">{{Harvtxt|Alon|Matias|Szegedy|1996}}</ref> इस पेपर के लिए, लेखकों ने बाद में स्ट्रीमिंग एल्गोरिदम में उनके मूलभूत योगदान के लिए 2005 में गोडेल पुरस्कार जीता। तब से डेटा स्ट्रीमिंग एल्गोरिदम के आसपास केंद्रित काम का एक बड़ा हिस्सा रहा है जो सिद्धांत, डेटाबेस, नेटवर्किंग और प्राकृतिक भाषा प्रसंस्करण जैसे कंप्यूटर विज्ञान क्षेत्रों के विविध स्पेक्ट्रम तक फैला हुआ है।
</ref> 1978 की शुरुआत में, साथ ही 1982/83 में [[फिलिप फ्लेजोलेट]] और जी. निगेल मार्टिन,<ref name=":0"/>स्ट्रीमिंग एल्गोरिदम के क्षेत्र को पहली बार 1996 में [[ सावधान अलोन |सावधान अलोन]] , [[योसी मतियास]] और [[मारियो सजेगेडी]] द्वारा एक पेपर में औपचारिक और लोकप्रिय बनाया गया था।<ref name=":1">{{Harvtxt|Alon|Matias|Szegedy|1996}}</ref> इस पेपर के लिए, लेखकों ने बाद में स्ट्रीमिंग एल्गोरिदम में उनके मूलभूत योगदान के लिए 2005 में गोडेल पुरस्कार जीता। तब से डेटा स्ट्रीमिंग एल्गोरिदम के आसपास केंद्रित काम का एक बड़ा हिस्सा रहा है जो सिद्धांत, डेटाबेस, नेटवर्किंग और प्राकृतिक भाषा प्रसंस्करण जैसे कंप्यूटर विज्ञान क्षेत्रों के विविध स्पेक्ट्रम तक फैला हुआ है।
[[अर्ध-स्ट्रीमिंग एल्गोरिथ्म]] को 2005 में ग्राफ़ के लिए स्ट्रीमिंग एल्गोरिदम में छूट के रूप में पेश किया गया था,<ref>{{Cite journal|last1=Feigenbaum|first1=Joan|last2=Sampath|first2=Kannan|date=2005|title=सेमी-स्ट्रीमिंग मॉडल में ग्राफ़ समस्याओं पर|url=https://dl.acm.org/citation.cfm?id=1132638|journal=Theoretical Computer Science|volume=348|issue=2|pages=207–216|doi=10.1016/j.tcs.2005.09.013|doi-access=free}}</ref> जिसमें अनुमत स्थान शीर्षों की संख्या में रैखिक है {{var|n}}, लेकिन किनारों की संख्या में केवल लघुगणक {{var|m}}. यह छूट घने ग्राफ़ के लिए अभी भी सार्थक है, और दिलचस्प समस्याओं (जैसे कनेक्टिविटी) को हल कर सकती है जो अघुलनशील हैं <math>o(n)</math> अंतरिक्ष।
[[अर्ध-स्ट्रीमिंग एल्गोरिथ्म]] को 2005 में ग्राफ़ के लिए स्ट्रीमिंग एल्गोरिदम में छूट के रूप में पेश किया गया था,<ref>{{Cite journal|last1=Feigenbaum|first1=Joan|last2=Sampath|first2=Kannan|date=2005|title=सेमी-स्ट्रीमिंग मॉडल में ग्राफ़ समस्याओं पर|url=https://dl.acm.org/citation.cfm?id=1132638|journal=Theoretical Computer Science|volume=348|issue=2|pages=207–216|doi=10.1016/j.tcs.2005.09.013|doi-access=free}}</ref> जिसमें अनुमत स्थान शीर्षों की संख्या में रैखिक है {{var|n}}, लेकिन किनारों की संख्या में केवल लघुगणक {{var|m}}. यह छूट घने ग्राफ़ के लिए अभी भी सार्थक है, और दिलचस्प समस्याओं (जैसे कनेक्टिविटी) को हल कर सकती है जो अघुलनशील हैं <math>o(n)</math> अंतरिक्ष।
Line 27:
Line 27:
=== डेटा स्ट्रीम मॉडल ===
=== डेटा स्ट्रीम मॉडल ===
डेटा स्ट्रीम मॉडल में, कुछ या सभी इनपुट को पूर्णांकों के एक सीमित अनुक्रम (कुछ परिमित डोमेन से) के रूप में दर्शाया जाता है, जो आम तौर पर यादृच्छिक पहुंच के लिए उपलब्ध नहीं होता है, बल्कि एक स्ट्रीम में एक समय में एक आता है।<ref>{{Cite book|last1=Babcock|first1=Brian|last2=Babu|first2=Shivnath|last3=Datar|first3=Mayur|last4=Motwani|first4=Rajeev|last5=Widom|first5=Jennifer|date=2002|title=डेटा स्ट्रीम सिस्टम में मॉडल और मुद्दे|journal=Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems|series=PODS '02|location=New York, NY, USA|publisher=ACM|pages=1–16|doi=10.1145/543613.543615|isbn=978-1581135077|citeseerx=10.1.1.138.190|s2cid=2071130}}</ref> यदि धारा की लंबाई है {{var|n}} और डोमेन का आकार है {{var|m}}, एल्गोरिदम आम तौर पर उस स्थान का उपयोग करने के लिए बाध्य होते हैं जो एल (जटिलता) में होता है {{var|m}} और {{var|n}}. वे आम तौर पर धारा के ऊपर केवल कुछ छोटी स्थिर संख्या में ही पास बना सकते हैं, कभी-कभी केवल एक-पास एल्गोरिथ्म।<ref>{{Cite book|last1=Bar-Yossef|first1=Ziv|last2=Jayram|first2=T. S.|last3=Kumar|first3=Ravi|last4=Sivakumar|first4=D.|author5-link=Luca Trevisan|last5=Trevisan|first5=Luca|date=2002-09-13|title=डेटा स्ट्रीम में विशिष्ट तत्वों की गिनती|journal=Randomization and Approximation Techniques in Computer Science|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=1–10|doi=10.1007/3-540-45726-7_1|isbn=978-3540457268|citeseerx=10.1.1.12.6276}}</ref>
डेटा स्ट्रीम मॉडल में, कुछ या सभी इनपुट को पूर्णांकों के एक सीमित अनुक्रम (कुछ परिमित डोमेन से) के रूप में दर्शाया जाता है, जो आम तौर पर यादृच्छिक पहुंच के लिए उपलब्ध नहीं होता है, बल्कि एक स्ट्रीम में एक समय में एक आता है।<ref>{{Cite book|last1=Babcock|first1=Brian|last2=Babu|first2=Shivnath|last3=Datar|first3=Mayur|last4=Motwani|first4=Rajeev|last5=Widom|first5=Jennifer|date=2002|title=डेटा स्ट्रीम सिस्टम में मॉडल और मुद्दे|journal=Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems|series=PODS '02|location=New York, NY, USA|publisher=ACM|pages=1–16|doi=10.1145/543613.543615|isbn=978-1581135077|citeseerx=10.1.1.138.190|s2cid=2071130}}</ref> यदि धारा की लंबाई है {{var|n}} और डोमेन का आकार है {{var|m}}, एल्गोरिदम आम तौर पर उस स्थान का उपयोग करने के लिए बाध्य होते हैं जो एल (जटिलता) में होता है {{var|m}} और {{var|n}}. वे आम तौर पर धारा के ऊपर केवल कुछ छोटी स्थिर संख्या में ही पास बना सकते हैं, कभी-कभी केवल एक-पास एल्गोरिथ्म।<ref>{{Cite book|last1=Bar-Yossef|first1=Ziv|last2=Jayram|first2=T. S.|last3=Kumar|first3=Ravi|last4=Sivakumar|first4=D.|author5-link=Luca Trevisan|last5=Trevisan|first5=Luca|date=2002-09-13|title=डेटा स्ट्रीम में विशिष्ट तत्वों की गिनती|journal=Randomization and Approximation Techniques in Computer Science|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=1–10|doi=10.1007/3-540-45726-7_1|isbn=978-3540457268|citeseerx=10.1.1.12.6276}}</ref>
=== टर्नस्टाइल और कैश रजिस्टर मॉडल ===
=== टर्नस्टाइल और कैश रजिस्टर मॉडल ===
अधिकांश स्ट्रीमिंग साहित्य आँकड़ों की गणना से संबंधित है
अधिकांश स्ट्रीमिंग साहित्य आँकड़ों की गणना से संबंधित है
आवृत्ति वितरण जो संग्रहीत करने के लिए बहुत बड़े हैं। इस वर्ग के लिए
आवृत्ति वितरण जो संग्रहीत करने के लिए बहुत बड़े हैं। इस वर्ग के लिए
Line 53:
Line 51:
=== स्लाइडिंग विंडो मॉडल ===
=== स्लाइडिंग विंडो मॉडल ===
कई पेपर स्लाइडिंग विंडो मॉडल पर भी विचार करते हैं।{{Citation needed|date=November 2017}} इस मॉडल में,
कई पेपर स्लाइडिंग विंडो मॉडल पर भी विचार करते हैं। इस मॉडल में,
रुचि का कार्य एक निश्चित आकार की विंडो पर कंप्यूटिंग करना है
रुचि का कार्य एक निश्चित आकार की विंडो पर कंप्यूटिंग करना है
धारा। जैसे-जैसे स्ट्रीम आगे बढ़ती है, विंडो के अंत से आइटम आते हैं
धारा। जैसे-जैसे स्ट्रीम आगे बढ़ती है, विंडो के अंत से आइटम आते हैं
Line 65:
Line 63:
धारा के क्रम पर (अर्थात, असममित कार्य), जैसे गिनती
धारा के क्रम पर (अर्थात, असममित कार्य), जैसे गिनती
एक धारा में व्युत्क्रमों की संख्या और सबसे लंबे समय तक बढ़ने का पता लगाना
एक धारा में व्युत्क्रमों की संख्या और सबसे लंबे समय तक बढ़ने का पता लगाना
परिणाम।{{citation needed|date=April 2021}}
परिणाम।
== मूल्यांकन ==
== मूल्यांकन ==
{{unreferenced section|date=April 2021}}
डेटा स्ट्रीम पर काम करने वाले एल्गोरिदम का प्रदर्शन तीन बुनियादी कारकों द्वारा मापा जाता है:
डेटा स्ट्रीम पर काम करने वाले एल्गोरिदम का प्रदर्शन तीन बुनियादी कारकों द्वारा मापा जाता है:
* एल्गोरिदम को स्ट्रीम के ऊपर से गुजरने की संख्या।
* एल्गोरिदम को स्ट्रीम के ऊपर से गुजरने की संख्या।
Line 79:
Line 76:
==अनुप्रयोग==
==अनुप्रयोग==
स्ट्रीमिंग एल्गोरिदम के [[ संगणक संजाल ]] में कई अनुप्रयोग हैं जैसे कि
स्ट्रीमिंग एल्गोरिदम के [[ संगणक संजाल |संगणक संजाल]] में कई अनुप्रयोग हैं जैसे कि
हाथियों के प्रवाह के लिए नेटवर्क लिंक की निगरानी करना, उनकी संख्या की गिनती करना
हाथियों के प्रवाह के लिए नेटवर्क लिंक की निगरानी करना, उनकी संख्या की गिनती करना
अलग-अलग प्रवाह, प्रवाह आकार के वितरण का अनुमान लगाना, इत्यादि
अलग-अलग प्रवाह, प्रवाह आकार के वितरण का अनुमान लगाना, इत्यादि
पर।<ref>{{Harvtxt|Xu|2007}}</ref> उनके पास एप्लिकेशन भी हैं
पर।<ref>{{Harvtxt|Xu|2007}}</ref> उनके पास एप्लिकेशन भी हैं
डेटाबेस, जैसे जॉइन के आकार का अनुमान लगाना (एसक्यूएल) {{Citation needed|date=March 2013}}.
डेटाबेस, जैसे जॉइन के आकार का अनुमान लगाना (एसक्यूएल)
<!--
==कुछ स्ट्रीमिंग समस्याएँ==
===आवृत्ति क्षण=== {{mvar|k}|k}}आवृत्तियों के एक सेट का वां आवृत्ति क्षण <math>\mathbf{a}</math> परिभाषित किया जाता है <math>F_k(\mathbf{a}) = \sum_{i=1}^n a_i^k</math>.
पहले पल <math>F_1</math> केवल आवृत्तियों का योग है (अर्थात, कुल गिनती)। दूसरा क्षण <math>F_2</math> डेटा के सांख्यिकीय गुणों की गणना के लिए उपयोगी है, जैसे कि [[गिनी गुणांक]]
भिन्नता का. <math>F_{\infty}</math> इसे सबसे अधिक बार आने वाली वस्तुओं की आवृत्ति के रूप में परिभाषित किया गया है।
एलोन, मटियास और सेजेडी के मौलिक पेपर ने आवृत्ति क्षणों का अनुमान लगाने की समस्या से निपटा।{{citation needed|date=April 2021}}
==== आवृत्ति क्षणों की गणना ====
आवृत्ति क्षणों को खोजने के लिए एक प्रत्यक्ष दृष्टिकोण के लिए एक रजिस्टर बनाए रखना आवश्यक है {{mvar|m<sub>i</sub>}} सभी विशिष्ट तत्वों के लिए {{math|''a''<sub>''i''</sub> ∈ (1,2,3,4,...,''N'')}} जिसके लिए कम से कम मेमोरी की आवश्यकता होती है
आदेश की <math>\Omega(N)</math>.<ref name=":1"/>लेकिन हमारे पास स्थान की सीमाएं हैं और हमें ऐसे एल्गोरिदम की आवश्यकता है जो बहुत कम मेमोरी में गणना करता हो। इसे सटीक मानों के बजाय सन्निकटन का उपयोग करके प्राप्त किया जा सकता है। एक एल्गोरिदम जो (ε,δ)अनुमान की गणना करता है {{mvar|F<sub>k</sub>}}, कहाँ {{mvar|F'<sub>k</sub>}} है (ε,δ)-
का अनुमानित मूल्य {{mvar|F<sub>k</sub>}}.<ref>{{Cite book|title = डेटा स्ट्रीम की आवृत्ति क्षणों का इष्टतम अनुमान|publisher = ACM|journal = Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing|date = 2005-01-01|location = New York, NY, USA|isbn = 978-1-58113-960-0|pages = 202–208|series = STOC '05|doi = 10.1145/1060590.1060621|first1 = Piotr|last1 = Indyk|first2 = David|last2 = Woodruff|s2cid = 7911758}}</ref> जहां ε सन्निकटन पैरामीटर है और δ आत्मविश्वास पैरामीटर है।<ref name=":2">{{Cite book|title = डेटा स्ट्रीम में विशिष्ट तत्वों की गिनती|publisher = Springer Berlin Heidelberg|date = 2002-09-13|isbn = 978-3-540-44147-2|pages = 1–10|series = Lecture Notes in Computer Science|first1 = Ziv|last1 = Bar-Yossef|first2 = T. S.|last2 = Jayram|first3 = Ravi|last3 = Kumar|first4 = D.|last4 = Sivakumar|first5 = Luca|last5 = Trevisan|editor-first = José D. P.|editor-last = Rolim|editor-first2 = Salil|editor-last2 = Vadhan|doi = 10.1007/3-540-45726-7_1|citeseerx = 10.1.1.12.6276}}</ref>
===== एफ की गणना<sub>0</sub> (डेटास्ट्रीम में विशिष्ट तत्व) =====
{{Main|Count-distinct problem}}
====== एफएम-स्केच एल्गोरिदम ======
फ्लेजोलेट एट अल. में <ref name=":0">{{Harvtxt|Flajolet|Martin|1985}}</ref> गिनती की संभाव्य पद्धति की शुरुआत की जो [[रॉबर्ट मॉरिस (क्रिप्टोग्राफर)]] के एक पेपर से प्रेरित थी।<ref>{{Harvtxt|Morris|1978}}</ref> मॉरिस अपने पेपर में कहते हैं कि यदि सटीकता की आवश्यकता को हटा दिया जाता है, तो एक काउंटर n को एक काउंटर द्वारा प्रतिस्थापित किया जा सकता है {{math|log ''n''}} जिसमें संग्रहित किया जा सकता है {{math|log log ''n''}} बिट्स.<ref>{{Cite journal|title = Approximate counting: A detailed analysis|journal = BIT Numerical Mathematics|date = 1985-03-01|issn = 0006-3835|pages = 113–134|volume = 25|issue = 1|doi = 10.1007/BF01934993|first = Philippe|last = Flajolet|citeseerx = 10.1.1.64.5320|s2cid = 2809103}}</ref> फ्लेजोलेट एट अल. में <ref name=":0" />हैश फ़ंक्शन का उपयोग करके इस पद्धति में सुधार किया गया {{mvar|h}} जिसे हैश स्पेस (लंबाई की एक बाइनरी स्ट्रिंग) में तत्व को समान रूप से वितरित करने के लिए माना जाता है {{mvar|L}}).
:<math>h:[m] \rightarrow [0,2^{L}-1]</math>
होने देना {{math|bit(''y,k'')}} बाइनरी प्रतिनिधित्व में kth बिट का प्रतिनिधित्व करते हैं {{mvar|y}}
मान लीजिए A लंबाई M की डेटा स्ट्रीम का अनुक्रम है जिसकी कार्डिनैलिटी निर्धारित करने की आवश्यकता है। मान लीजिए बिटमैप [0...L − 1] है
हैश स्पेस जहां {{mvar|ρ}}(हैशेडवैल्यू) रिकॉर्ड किए जाते हैं। नीचे दिया गया एल्गोरिदम A.<pre> की अनुमानित कार्डिनैलिटी निर्धारित करता है
प्रक्रिया एफएम-स्केच:
i के लिए 0 से L − 1 तक करें
बिटमैप[i] := 0
के लिए समाप्त
ए में एक्स के लिए: करो
सूचकांक := ρ(हैश(x))
यदि बिटमैप[सूचकांक] = 0 तो
बिटमैप[सूचकांक] := 1
अगर अंत
के लिए समाप्त
बी := बिटमैप के सबसे बाएं 0 बिट की स्थिति[]
वापसी 2 ^ बी
</pre>यदि डेटा स्ट्रीम में N विशिष्ट तत्व हैं।
* के लिए <math>i \gg \log(N)</math> तो BITMAP[i] निश्चित रूप से 0 है
* के लिए <math>i \ll \log(N)</math> तो बिटमैप[i] निश्चित रूप से 1 है
* के लिए <math>i \approx \log(N)</math> तो BITMAP[i] 0 और 1 की एक सीमा है
====== के-न्यूनतम मूल्य एल्गोरिथ्म ======
पिछला एल्गोरिदम एफ का अनुमान लगाने के पहले प्रयास का वर्णन करता है<sub>0</sub> फ़्लैजोलेट और मार्टिन द्वारा डेटा स्ट्रीम में। उनका एल्गोरिदम एक यादृच्छिक [[हैश फंकशन]] चुनता है जिसे वे हैश मानों को हैश स्पेस में समान रूप से वितरित करने के लिए मानते हैं।
बार-योसेफ एट अल. में <ref name=":2" />डेटा स्ट्रीम में अलग-अलग तत्वों की संख्या निर्धारित करने के लिए k-न्यूनतम मान एल्गोरिदम पेश किया गया। उन्होंने एक समान हैश फ़ंक्शन h का उपयोग किया जिसे [0,1] के रूप में सामान्यीकृत किया जा सकता है <math>h:[m] \rightarrow [0,1]</math>. लेकिन उन्होंने हैश स्पेस में मानों की संख्या के लिए एक सीमा तय की। T का मान क्रम का माना जाता है <math>O\left(\dfrac{1}{\varepsilon_{2}}\right)</math> (अर्थात् कम सन्निकटन-मान ε के लिए अधिक t की आवश्यकता होती है)। KMV एल्गोरिदम हैश स्पेस में केवल t-सबसे छोटा हैश मान रखता है। धारा के सभी m मान आ जाने के बाद, <math>\upsilon= \mathrm{Max}(h(a_{i} ))</math> गणना करने के लिए उपयोग किया जाता है<math>F'_{0}=\dfrac{t}{\upsilon}</math>. यानी, एक समान हैश स्पेस में, वे कम से कम टी तत्वों से कम होने की उम्मीद करते हैं <math>O\left(\dfrac{t}{F_{0}}\right)</math>.<पूर्व>
प्रक्रिया 2 के-न्यूनतम मूल्य
KMV के पहले t मान प्रारंभ करें
एक में एक करने के लिए एक के लिए
यदि h(a) <अधिकतम(KMV) तो
KMV सेट से Max(KMV) हटाएँ
केएमवी में एच(ए) डालें
अगर अंत
के लिए समाप्त
वापसी टी/अधिकतम(केएमवी)
</पूर्व>
====== केएमवी का जटिलता विश्लेषण ======
KMV एल्गोरिदम को कार्यान्वित किया जा सकता है <math>O\left(\left(\dfrac{1}{\varepsilon_{2}}\right)\cdot\log(m)\right)</math> मेमोरी बिट्स स्पेस. प्रत्येक हैश मान के लिए ऑर्डर के स्थान की आवश्यकता होती है <math>O(\log(m))</math> मेमोरी बिट्स. ऑर्डर के हैश मान हैं <math>O\left(\dfrac{1}{\varepsilon_{2}}\right)</math>. यदि हम टी हैश मानों को बाइनरी ट्री में संग्रहीत करते हैं तो एक्सेस समय कम किया जा सकता है। इस प्रकार समय की जटिलता कम हो जाएगी <math>O\left(\log\left(\dfrac{1}{\varepsilon}\right)\cdot\log(m)\right)</math>.
===== गणना {{math|''F''<sub>k</sub>}} =====
अलोन एट अल. डार्लिंग्स {{mvar|F<sub>k</sub>}} यादृच्छिक चर को परिभाषित करके जिनकी गणना दिए गए स्थान और समय के भीतर की जा सकती है।<ref name=":1" />यादृच्छिक चर का अपेक्षित मान अनुमानित मान देता है {{mvar|F<sub>k</sub>}}.
मान लें कि अनुक्रम m की लंबाई पहले से ज्ञात है। फिर निम्नानुसार एक यादृच्छिक चर X का निर्माण करें:
* चुनना {{mvar|a<sub>p</sub>}} अनुक्रम का एक यादृच्छिक सदस्य बनें {{mvar|A}} सूचकांक के साथ {{mvar|p}}, <math>a_p=l \in(1,2,3,\ldots,n)</math>
* होने देना <math>r=|\{q:q\geq p,a_q=l\}|</math>, की घटनाओं की संख्या का प्रतिनिधित्व करता है {{mvar|l}} अनुक्रम के सदस्यों के भीतर {{mvar|A}} अगले {{mvar|a<sub>p</sub>}}.
* अनियमित परिवर्तनशील वस्तु <math>X=m(r^k-(r-1)^k)</math>.
मान लीजिए एस<sub>1</sub> आदेश का हो <math>O(n^{1-1/k}/\lambda^{2})</math> और एस<sub>2</sub> आदेश का हो <math>O(\log(1/\varepsilon))</math>. एल्गोरिथम एस लेता है<sub>2</sub> अनियमित परिवर्तनशील वस्तु <math>Y_1,Y_2,...,Y_{S2}</math> और माध्यिका को आउटपुट करता है <math>Y</math> . कहाँ {{mvar|Y<sub>i</sub>}} का औसत है {{mvar|X<sub>ij</sub>}} जहां 1 ≤ जे ≤ एस<sub>1</sub>.
अब यादृच्छिक चर की अपेक्षा की गणना करें {{math|''E''(''X'')}}.
====== की जटिलता {{math|''F''<sub>k</sub>}} ======
गणना करने के लिए एल्गोरिदम से {{mvar|F<sub>k</sub>}} ऊपर चर्चा की गई है, हम देख सकते हैं कि प्रत्येक यादृच्छिक चर {{mvar|X}} का मूल्य संग्रहीत करता है {{mvar|a<sub>p</sub>}} और {{mvar|r}}. तो, गणना करने के लिए {{mvar|X}}हमें केवल बनाए रखने की जरूरत है {{math|log(''n'')}}भंडारण के लिए बिट्स {{mvar|a<sub>p</sub>}} और {{math|log(''n'')}}भंडारण के लिए बिट्स {{mvar|r}}. यादृच्छिक चर की कुल संख्या {{mvar|X}} यह होंगे {{tmath|S_1 * S_2}}.
इसलिए एल्गोरिदम द्वारा ली गई कुल स्थान जटिलता इस क्रम की है <math>O\left(\dfrac{k\log{1 \over \varepsilon}}{\lambda^{2}}n^{1-{1 \over k}}\left(\log n + \log m\right)\right)</math>
====== गणना करने का सरल तरीका {{math|''F''<sub>2</sub>}} ======
पिछला एल्गोरिदम गणना करता है <math>F_2</math> के क्रम में <math>O( \sqrt{n}(\log m + \log n))</math> मेमोरी बिट्स. अलोन एट अल. में <ref name=":1" />मैप किए गए मानों के साथ चार-वार स्वतंत्र यादृच्छिक चर का उपयोग करके इस एल्गोरिदम को सरल बनाया गया <math>\{-1,1\}</math>.
इससे गणना करने की जटिलता और भी कम हो जाती है <math>F_2</math> को <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>
===बारंबार तत्व===
डेटा स्ट्रीम मॉडल में, लगातार तत्वों की समस्या उन तत्वों के एक सेट को आउटपुट करना है जो स्ट्रीम के कुछ निश्चित अंश से अधिक का गठन करते हैं। एक विशेष मामला बहुसंख्यक समस्या है, जो यह निर्धारित करना है कि कोई मान धारा के बहुमत का गठन करता है या नहीं।
अधिक औपचारिक रूप से, कुछ सकारात्मक स्थिरांक तय करें {{var|c}} > 1, मान लीजिए धारा की लंबाई है {{var|m}}, और जाने {{var|f}}<sub>{{var|i}}</sub> मूल्य की आवृत्ति को निरूपित करें {{var|i}} धारा में. लगातार तत्वों की समस्या [[सेट (गणित)]] को आउटपुट करना है { {{var|i}} | {{var|f}}<sub>{{var|i}}</sub> >एम/सी }.<ref>{{Cite book|title=एल्गोरिदम का विश्वकोश|last=Cormode|first=Graham|date=2014|publisher=Springer US|isbn=9783642278488|editor-last=Kao|editor-first=Ming-Yang|pages=1–5|language=en|doi=10.1007/978-3-642-27848-8_572-1|chapter = Misra-Gries Summaries}}</ref>
कुछ उल्लेखनीय एल्गोरिदम हैं:
* बॉयर-मूर बहुमत वोट एल्गोरिदम
* [[काउंट-मिन स्केच]]
* [[हानिपूर्ण गणना एल्गोरिदम]]
* मल्टी-स्टेज [[ब्लूम फिल्टर]]
* मिश्रा-ग्रिज़ हेवी हिटर्स एल्गोरिदम
* मिश्रा-ग्रिज़ सारांश
===घटना का पता लगाना===
डेटा स्ट्रीम में घटनाओं का पता लगाना अक्सर हेवी हिटर्स एल्गोरिदम का उपयोग करके किया जाता है जैसा कि ऊपर सूचीबद्ध किया गया है: सबसे लगातार आइटम और उनकी आवृत्ति इन एल्गोरिदम में से एक का उपयोग करके निर्धारित की जाती है, फिर पिछले समय बिंदु की तुलना में सबसे बड़ी वृद्धि को प्रवृत्ति के रूप में रिपोर्ट किया जाता है। सामान्यीकरण के लिए घातीय रूप से भारित चलती औसत और विचरण का उपयोग करके इस दृष्टिकोण को परिष्कृत किया जा सकता है।<ref>{{Cite conference | doi = 10.1145/2623330.2623740| title = SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds| conference = Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14| pages = 871–880| year = 2014| last1 = Schubert | first1 = E. | last2 = Weiler | first2 = M. | last3 = Kriegel | first3 = H. P. | author-link3 = Hans-Peter Kriegel| isbn = 9781450329569}}</ref>
===विभिन्न तत्वों की गिनती===
एक स्ट्रीम में अलग-अलग तत्वों की संख्या की गणना करना (कभी-कभी इसे कहा जाता है)।
{{math|''F''<sub>0</sub>}}पल) एक और समस्या है जिसका अच्छी तरह से अध्ययन किया गया है।
इसके लिए पहला एल्गोरिदम फ्लैजोलेट और मार्टिन द्वारा प्रस्तावित किया गया था। 2010 में, डैनियल केन (गणितज्ञ), [[ स्पष्टीकरण नेल्सन ]] और डेविड वुड्रूफ़ ने इस समस्या के लिए एक असम्बद्ध रूप से इष्टतम एल्गोरिदम पाया।<ref>{{Harvtxt|Kane|Nelson|Woodruff|2010}}</ref> यह उपयोगकर्ता है {{math|''O''(''ε''<sup>2</sup> + log ''d'')}} अंतरिक्ष, साथ {{math|''O''(1)}} सबसे खराब स्थिति में अद्यतन और रिपोर्टिंग समय, साथ ही सार्वभौमिक हैश फ़ंक्शंस और ए {{mvar|r}}-वार स्वतंत्र हैश परिवार जहां {{math|1=''r'' = Ω(log(1/''ε'') / log log(1/''ε''))}}.
===एंट्रॉपी===
आवृत्तियों के एक सेट की (अनुभवजन्य) एन्ट्रापी <math>\mathbf{a}</math> है
के रूप में परिभाषित <math>F_k(\mathbf{a}) = \sum_{i=1}^n
| journal = Communications of the ACM| s2cid = 36226357 }}.
{{Algorithmic paradigms}}
[[Category: स्ट्रीमिंग एल्गोरिदम]]
[[Category: Machine Translated Page]]
.
[[Category:Created On 07/07/2023]]
Revision as of 11:13, 20 July 2023
कंप्यूटर विज्ञान में, स्ट्रीमिंग एल्गोरिदम आकड़ों का प्रवाह को संसाधित करने के लिए एल्गोरिदम हैं जिसमें इनपुट को वस्तुओं के अनुक्रम के रूप में प्रस्तुत किया जाता है और केवल कुछ पासों में जांच की जा सकती है, आमतौर पर एक-पास एल्गोरिथ्म इन एल्गोरिदम को सीमित मेमोरी के साथ संचालित करने के लिए डिज़ाइन किया गया है, आम तौर पर स्ट्रीम के आकार में एल (जटिलता) और/या स्ट्रीम में अधिकतम मूल्य, और प्रति आइटम सीमित प्रसंस्करण समय भी हो सकता है।
इन बाधाओं के परिणामस्वरूप, स्ट्रीमिंग एल्गोरिदम अक्सर डेटा स्ट्रीम के सारांश या स्केच के आधार पर अनुमानित उत्तर देते हैं।
हालाँकि स्ट्रीमिंग एल्गोरिदम का अध्ययन मुनरो और पैटरसन द्वारा पहले ही किया जा चुका था[1] 1978 की शुरुआत में, साथ ही 1982/83 में फिलिप फ्लेजोलेट और जी. निगेल मार्टिन,[2]स्ट्रीमिंग एल्गोरिदम के क्षेत्र को पहली बार 1996 में सावधान अलोन , योसी मतियास और मारियो सजेगेडी द्वारा एक पेपर में औपचारिक और लोकप्रिय बनाया गया था।[3] इस पेपर के लिए, लेखकों ने बाद में स्ट्रीमिंग एल्गोरिदम में उनके मूलभूत योगदान के लिए 2005 में गोडेल पुरस्कार जीता। तब से डेटा स्ट्रीमिंग एल्गोरिदम के आसपास केंद्रित काम का एक बड़ा हिस्सा रहा है जो सिद्धांत, डेटाबेस, नेटवर्किंग और प्राकृतिक भाषा प्रसंस्करण जैसे कंप्यूटर विज्ञान क्षेत्रों के विविध स्पेक्ट्रम तक फैला हुआ है।
अर्ध-स्ट्रीमिंग एल्गोरिथ्म को 2005 में ग्राफ़ के लिए स्ट्रीमिंग एल्गोरिदम में छूट के रूप में पेश किया गया था,[4] जिसमें अनुमत स्थान शीर्षों की संख्या में रैखिक है n, लेकिन किनारों की संख्या में केवल लघुगणक m. यह छूट घने ग्राफ़ के लिए अभी भी सार्थक है, और दिलचस्प समस्याओं (जैसे कनेक्टिविटी) को हल कर सकती है जो अघुलनशील हैं अंतरिक्ष।
मॉडल
डेटा स्ट्रीम मॉडल
डेटा स्ट्रीम मॉडल में, कुछ या सभी इनपुट को पूर्णांकों के एक सीमित अनुक्रम (कुछ परिमित डोमेन से) के रूप में दर्शाया जाता है, जो आम तौर पर यादृच्छिक पहुंच के लिए उपलब्ध नहीं होता है, बल्कि एक स्ट्रीम में एक समय में एक आता है।[5] यदि धारा की लंबाई है n और डोमेन का आकार है m, एल्गोरिदम आम तौर पर उस स्थान का उपयोग करने के लिए बाध्य होते हैं जो एल (जटिलता) में होता है m और n. वे आम तौर पर धारा के ऊपर केवल कुछ छोटी स्थिर संख्या में ही पास बना सकते हैं, कभी-कभी केवल एक-पास एल्गोरिथ्म।[6]
टर्नस्टाइल और कैश रजिस्टर मॉडल
अधिकांश स्ट्रीमिंग साहित्य आँकड़ों की गणना से संबंधित है
आवृत्ति वितरण जो संग्रहीत करने के लिए बहुत बड़े हैं। इस वर्ग के लिए
समस्याएँ, एक वेक्टर है
(शून्य वेक्टर से प्रारंभ किया गया ) जिसमें अपडेट हैं
इसे एक स्ट्रीम में प्रस्तुत किया गया। इन एल्गोरिदम का लक्ष्य गणना करना है
के कार्य इसकी तुलना में काफी कम जगह का उपयोग करना
प्रतिनिधित्व करने के लिए ले जाएगा एकदम सही। वहाँ दो हैं
ऐसी धाराओं को अद्यतन करने के लिए सामान्य मॉडल, जिन्हें कैश रजिस्टर कहा जाता है और
कैश रजिस्टर मॉडल में, प्रत्येक अद्यतन प्रपत्र का होता है , ताकि कुछ सकारात्मकता से वृद्धि हुई है
पूर्णांक . एक उल्लेखनीय विशेष मामला है जब
(केवल इकाई सम्मिलन की अनुमति है)।
टर्नस्टाइल मॉडल में, प्रत्येक अद्यतन प्रपत्र का होता है , ताकि कुछ (संभवतः नकारात्मक) पूर्णांक द्वारा वृद्धि की जाती है . सख्त टर्नस्टाइल मॉडल में, नहीं
किसी भी समय शून्य से कम हो सकता है.
स्लाइडिंग विंडो मॉडल
कई पेपर स्लाइडिंग विंडो मॉडल पर भी विचार करते हैं। इस मॉडल में,
रुचि का कार्य एक निश्चित आकार की विंडो पर कंप्यूटिंग करना है
धारा। जैसे-जैसे स्ट्रीम आगे बढ़ती है, विंडो के अंत से आइटम आते हैं
विचार से हटा दिया गया जबकि स्ट्रीम से नए आइटम अपना ले लिए गए
जगह।
उपरोक्त आवृत्ति-आधारित समस्याओं के अलावा, कुछ अन्य प्रकार की समस्याएं
का भी अध्ययन किया गया है। सेटिंग में कई ग्राफ़ समस्याओं का समाधान किया जाता है
जहां आसन्न मैट्रिक्स या ग्राफ़ की आसन्न सूची स्ट्रीम की जाती है
कुछ अज्ञात आदेश. कुछ समस्याएँ ऐसी भी होती हैं जो अत्यधिक निर्भर होती हैं
धारा के क्रम पर (अर्थात, असममित कार्य), जैसे गिनती
एक धारा में व्युत्क्रमों की संख्या और सबसे लंबे समय तक बढ़ने का पता लगाना
परिणाम।
मूल्यांकन
डेटा स्ट्रीम पर काम करने वाले एल्गोरिदम का प्रदर्शन तीन बुनियादी कारकों द्वारा मापा जाता है:
एल्गोरिदम को स्ट्रीम के ऊपर से गुजरने की संख्या।
उपलब्ध स्मृति.
एल्गोरिदम का चलने का समय।
इन एल्गोरिदम में ऑनलाइन एल्गोरिदम के साथ कई समानताएं हैं क्योंकि इन दोनों को सभी डेटा उपलब्ध होने से पहले निर्णय लेने की आवश्यकता होती है, लेकिन वे समान नहीं हैं। डेटा स्ट्रीम एल्गोरिदम में केवल सीमित मेमोरी उपलब्ध होती है, लेकिन वे बिंदुओं के समूह के आने तक कार्रवाई को स्थगित करने में सक्षम हो सकते हैं, जबकि ऑनलाइन एल्गोरिदम को प्रत्येक बिंदु के आते ही कार्रवाई करने की आवश्यकता होती है।
यदि एल्गोरिदम एक सन्निकटन एल्गोरिदम है तो उत्तर की सटीकता एक अन्य महत्वपूर्ण कारक है। सटीकता को अक्सर एक के रूप में बताया जाता है सन्निकटन का अर्थ है कि एल्गोरिदम इससे कम की त्रुटि प्राप्त करता है संभाव्यता के साथ .
अनुप्रयोग
स्ट्रीमिंग एल्गोरिदम के संगणक संजाल में कई अनुप्रयोग हैं जैसे कि
हाथियों के प्रवाह के लिए नेटवर्क लिंक की निगरानी करना, उनकी संख्या की गिनती करना
अलग-अलग प्रवाह, प्रवाह आकार के वितरण का अनुमान लगाना, इत्यादि
पर।[8] उनके पास एप्लिकेशन भी हैं
डेटाबेस, जैसे जॉइन के आकार का अनुमान लगाना (एसक्यूएल)
.
↑
Munro, J. Ian; Paterson, Mike (1978). "Selection and Sorting with Limited Storage". 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16–18 October 1978. IEEE Computer Society. pp. 253–258. doi:10.1109/SFCS.1978.32.
↑Cite error: Invalid <ref> tag; no text was provided for refs named :0
