स्ट्रीमिंग एल्गोरिदम: Difference between revisions

Latest revision as of 10:17, 2 August 2023

कंप्यूटर विज्ञान में, स्ट्रीमिंग एल्गोरिदम डेटा स्ट्रीम को संसाधित करने के लिए एक एल्गोरिदम होता हैं जिसमें इनपुट को वस्तुओं के अनुक्रम के रूप में प्रस्तुत किया जाता है और मात्र कुछ पस्सेस में जांच की जा सकती है, सामान्यतः मात्र एकल एल्गोरिदम मर प्रस्तुत किया जाता है। इन एल्गोरिदम को सीमित मेमोरी के साथ संचालित करने के लिए निर्मित किया जाता है, सामान्यतः पर स्ट्रीम के आकार में और/या स्ट्रीम में अधिकतम मूल्य, और प्रति वस्तु सीमित प्रसंस्करण समय भी हो सकता है।

इन बाधाओं के परिणामस्वरूप, स्ट्रीमिंग एल्गोरिदम अक्सर डेटा स्ट्रीम के सारांश या स्केच के आधार पर अनुमानित उत्तर देते हैं।

इतिहास

यघपि स्ट्रीमिंग एल्गोरिदम का अध्ययन मुनरो और पैटरसन द्वारा 1978 के प्रारम्भ में पहले ही किया जा चुका था,^[1] साथ ही 1982/83 में फिलिप फ्लेजोलेट और जी निगेल मार्टिन द्वारा भी,स्ट्रीमिंग एल्गोरिदम के क्षेत्र को सर्वप्रथम 1996 में नोगा अलोन, योसी मतियास और मारियो सजेगेडी द्वारा एक पेपर में औपचारिक और लोकप्रिय बनाया गया था।^[2] इस पेपर के लिए, लेखकों ने बाद में स्ट्रीमिंग एल्गोरिदम में उनके मूलभूत योगदान के लिए 2005 में गोडेल पुरस्कार जीता। तब से डेटा स्ट्रीमिंग एल्गोरिदम के आसपास केंद्रित काम का एक बड़ा भाग रहा है जो सिद्धांत, डेटाबेस, नेटवर्किंग और प्राकृतिक भाषा प्रसंस्करण जैसे कंप्यूटर विज्ञान क्षेत्रों के विविध स्पेक्ट्रम तक प्रसारित हुआ है।

अर्ध-स्ट्रीमिंग एल्गोरिथ्म को 2005 में ग्राफ़ के लिए स्ट्रीमिंग एल्गोरिदम में छूट(रियायत) के रूप में प्रस्तुत किया गया था,^[3] जिसमें अनुमत स्थान शीर्षों की संख्या में रैखिक n होते है, परन्तु किनारों की संख्या mमें मात्र लघुगणक होते है। यह छूट घने ग्राफ़ के लिए अभी भी सार्थक है, और रुचिकर समस्याओं (जैसे कनेक्टिविटी) को हल कर सकती है जो $o(n)$ स्थान में अघुलनशील होता हैं ।

मॉडल

डेटा स्ट्रीम मॉडल

डेटा स्ट्रीम मॉडल में, कुछ या सभी इनपुट को पूर्णांकों के एक सीमित अनुक्रम (कुछ परिमित डोमेन से) के रूप में प्रदर्शित किया जाता है, जो सामान्यतः यादृच्छिक पहुंच के लिए उपलब्ध नहीं होता है, जबकि एक स्ट्रीम में एक समय में एक आता है।^[4] यदि स्ट्रीम की लंबाई n है और डोमेन का आकार m है, तो एल्गोरिदम सामान्यतः m और n में लॉगरिदमिक स्थान का उपयोग करने के लिए बाध्य होते हैं। वे सामान्यतः स्ट्रीम के ऊपर मात्र कुछ छोटी स्थिर संख्या में ही पास बना सकते हैं, कभी-कभी मात्र एक-पास एल्गोरिथ्म निर्मित कर सकते है।^[5]

टर्नस्टाइल और कैश रजिस्टर मॉडल

अधिकांश स्ट्रीमिंग साहित्य आँकड़ों की गणना से संबंधित होता है जो संग्रहीत करने के लिए बहुत बड़े होते हैं। समस्याओं के इस वर्ग के लिए, एक सदिश $\mathbf {a} =(a_{1},\dots ,a_{n})$ ( $\mathbf {0}$ शून्य सदिश से प्रारंभ किया गया ) होता है जिसमें अपडेट स्ट्रीम में प्रस्तुत किया जाता है। इन एल्गोरिदम का लक्ष्य गणना करना और $\mathbf {a}$ के कार्य की तुलना में अधिक कम स्थान का उपयोग करना होता है। $\mathbf {a}$ प्रतिनिधित्व करने के लिए लगने वाली स्थान से अधिक कम स्थान का उपयोग कर रहा है। स्पष्ट रूप से ऐसी स्ट्रीम ओं को अद्यतन करने के लिए दो सामान्य मॉडल हैं, जिन्हें "कैश रजिस्टर" और "टर्नस्टाइल" मॉडल कहा जाता है।^[6]कैश रजिस्टर मॉडल में, प्रत्येक अद्यतन प्रपत्र का $\langle i,c\rangle$ होता है, जिससे $a_{i}$ कुछ धनात्मक से वृद्धि होती है इस प्रकार $c$ पूर्णांक होता है। एक उल्लेखनीय विशेष स्थिति जब होती है तब $c=1$ होता (मात्र इकाई सम्मिलन की अनुमति होती है)।

टर्नस्टाइल मॉडल में, प्रत्येक अद्यतन प्रपत्र का $\langle i,c\rangle$ होता है , जिससे $a_{i}$ कुछ (संभवतः नकारात्मक) पूर्णांक $c$ द्वारा वृद्धि की जाती है। कठोर टर्नस्टाइल मॉडल में, ननो $a_{i}$ किसी भी समय शून्य से कम हो सकता है.

स्लाइडिंग विंडो मॉडल

कई पेपर "स्लाइडिंग विंडो" मॉडल पर भी विचार करते हैं। इस मॉडल में, रुचि का कार्य एक निश्चित आकार की विंडो पर कंप्यूटिंग करना होता है जैसे-जैसे स्ट्रीम आगे बढ़ती है, विंडो के अंत से वस्तु विचार से हटा दिए जाते है गया जबकि स्ट्रीम से नई वस्तुएं उनका स्थान ले लेते है।

उपरोक्त आवृत्ति-आधारित समस्याओं के अतिरिक्त, कुछ अन्य प्रकार की समस्याएं का भी अध्ययन किया जाताहै। सेटिंग में कई ग्राफ़ समस्याओं का समाधान किया जाता है जहां आसन्न आव्युह या ग्राफ़ की आसन्न सूची स्ट्रीम की जाती है। समस्याएँ ऐसी भी होती हैं जो स्ट्रीम के क्रम (अर्थात, असममित कार्य) पर बहुत अधिक निर्भर होती हैं, जैसे एक स्ट्रीम में व्युत्क्रमों की संख्या और सबसे लंबे समय तक बढ़ने वाले अनुवर्ती का पता लगाना।

मूल्यांकन

डेटा स्ट्रीम पर काम करने वाले एल्गोरिदम का प्रदर्शन तीन मूलभूत कारकों द्वारा मापा जाता है:

एल्गोरिदम को स्ट्रीम के ऊपर से पारित होने की संख्या।
उपलब्ध स्मृति।
एल्गोरिदम का चलने का समय।

इन एल्गोरिदम में ऑनलाइन एल्गोरिदम के साथ कई समानताएं होती हैं क्योंकि इन दोनों को सभी डेटा उपलब्ध होने से पहले निर्णय लेने की आवश्यकता होती है, लेकिन वे समान नहीं होते हैं। डेटा स्ट्रीम एल्गोरिदम में मात्र सीमित मेमोरी उपलब्ध होती है, परन्तु वे बिंदुओं के समूह के आने तक संचालन को स्थगित करने में सक्षम हो सकते हैं, जबकि ऑनलाइन एल्गोरिदम को प्रत्येक बिंदु के आते ही संचालन करने की आवश्यकता होती है।

यदि एल्गोरिदम एक सन्निकटन एल्गोरिदम है तो उत्तर की त्रुटिहीनता एक अन्य महत्वपूर्ण कारक होता है। त्रुटिहीनता को अधिकांशतः एक के रूप में बताया जाता है $(\epsilon ,\delta )$ सन्निकटन का अर्थ है कि एल्गोरिदम इससे कम की त्रुटि $\epsilon$ संभाव्यता के साथ $1-\delta$ प्राप्त करता है।

अनुप्रयोग

स्ट्रीमिंग एल्गोरिदम के नेटवर्किंग में कई अनुप्रयोग होते हैं जैसे कि एलीफैंट के प्रवाह के लिए नेटवर्क लिंक की जांच करना, उनकी संख्या की गिनती करना, अलग-अलग प्रवाह आकार के वितरण का अनुमान लगाना, इत्यादि।^[7] उनके पास डेटाबेस में अनुप्रयोग भी होते हैं, जैसे जॉइन के आकार का अनुमान लगाना होता है।

.

↑ 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.
↑ Alon, Matias & Szegedy (1996)
↑ Feigenbaum, Joan; Sampath, Kannan (2005). "सेमी-स्ट्रीमिंग मॉडल में ग्राफ़ समस्याओं पर". Theoretical Computer Science. 348 (2): 207–216. doi:10.1016/j.tcs.2005.09.013.
↑ Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). डेटा स्ट्रीम सिस्टम में मॉडल और मुद्दे. pp. 1–16. CiteSeerX 10.1.1.138.190. doi:10.1145/543613.543615. ISBN 978-1581135077. S2CID 2071130. {{cite book}}: |journal= ignored (help)
↑ Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). डेटा स्ट्रीम में विशिष्ट तत्वों की गिनती. pp. 1–10. CiteSeerX 10.1.1.12.6276. doi:10.1007/3-540-45726-7_1. ISBN 978-3540457268. {{cite book}}: |journal= ignored (help)
↑ Gilbert et al. (2001)
↑ Xu (2007)

[1] 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.

[:1-2] Alon, Matias & Szegedy (1996)

[3] Feigenbaum, Joan; Sampath, Kannan (2005). "सेमी-स्ट्रीमिंग मॉडल में ग्राफ़ समस्याओं पर". Theoretical Computer Science. 348 (2): 207–216. doi:10.1016/j.tcs.2005.09.013.

[4] Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). डेटा स्ट्रीम सिस्टम में मॉडल और मुद्दे. pp. 1–16. CiteSeerX 10.1.1.138.190. doi:10.1145/543613.543615. ISBN 978-1581135077. S2CID 2071130. {{cite book}}: |journal= ignored (help)

[5] Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). डेटा स्ट्रीम में विशिष्ट तत्वों की गिनती. pp. 1–10. CiteSeerX 10.1.1.12.6276. doi:10.1007/3-540-45726-7_1. ISBN 978-3540457268. {{cite book}}: |journal= ignored (help)

[6] Gilbert et al. (2001)

[7] Xu (2007)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Anonymous

Search

स्ट्रीमिंग एल्गोरिदम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:17, 2 August 2023

Contents

इतिहास

मॉडल

डेटा स्ट्रीम मॉडल

टर्नस्टाइल और कैश रजिस्टर मॉडल

स्लाइडिंग विंडो मॉडल

मूल्यांकन

अनुप्रयोग

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
-[[कंप्यूटर विज्ञान]] में, स्ट्रीमिंग एल्गोरिदम [[आकड़ों का प्रवाह]] को संसाधित करने के लिए एल्गोरिदम हैं जिसमें इनपुट को वस्तुओं के [[अनुक्रम]] के रूप में प्रस्तुत किया जाता है और केवल कुछ पासों में जांच की जा सकती है, आमतौर पर [[एक-पास एल्गोरिथ्म]] इन एल्गोरिदम को सीमित मेमोरी के साथ संचालित करने के लिए डिज़ाइन किया गया है, आम तौर पर स्ट्रीम के आकार में [[एल (जटिलता)]] और/या स्ट्रीम में अधिकतम मूल्य, और प्रति आइटम सीमित प्रसंस्करण समय भी हो सकता है।
+[[कंप्यूटर विज्ञान]] में, '''स्ट्रीमिंग एल्गोरिदम''' [[आकड़ों का प्रवाह|डेटा स्ट्रीम]] को संसाधित करने के लिए एक एल्गोरिदम होता हैं जिसमें इनपुट को वस्तुओं के [[अनुक्रम]] के रूप में प्रस्तुत किया जाता है और मात्र कुछ पस्सेस में जांच की जा सकती है, सामान्यतः [[एक-पास एल्गोरिथ्म|मात्र एकल]] एल्गोरिदम मर प्रस्तुत किया जाता है। इन एल्गोरिदम को सीमित मेमोरी के साथ संचालित करने के लिए निर्मित किया जाता है, सामान्यतः पर स्ट्रीम के आकार में और/या स्ट्रीम में अधिकतम मूल्य, और प्रति वस्तु सीमित प्रसंस्करण समय भी हो सकता है।
 इन बाधाओं के परिणामस्वरूप, स्ट्रीमिंग एल्गोरिदम अक्सर डेटा स्ट्रीम के सारांश या स्केच के आधार पर अनुमानित उत्तर देते हैं।
@@ Line 7: / Line 7: @@
 ==इतिहास==
-हालाँकि स्ट्रीमिंग एल्गोरिदम का अध्ययन मुनरो और पैटरसन द्वारा पहले ही किया जा चुका था<ref>
+यघपि स्ट्रीमिंग एल्गोरिदम का अध्ययन मुनरो और पैटरसन द्वारा 1978 के प्रारम्भ में पहले ही किया जा चुका था,<ref>
 {{cite conference
 | title = Selection and Sorting with Limited Storage
@@ Line 19: / Line 19: @@
 | pages = 253–258
 |doi = 10.1109/SFCS.1978.32}}
-</ref> 1978 की शुरुआत में, साथ ही 1982/83 में [[फिलिप फ्लेजोलेट]] और जी. निगेल मार्टिन,<ref name=":0"/>स्ट्रीमिंग एल्गोरिदम के क्षेत्र को पहली बार 1996 में [[ सावधान अलोन ]], [[योसी मतियास]] और [[मारियो सजेगेडी]] द्वारा एक पेपर में औपचारिक और लोकप्रिय बनाया गया था।<ref name=":1">{{Harvtxt|Alon|Matias|Szegedy|1996}}</ref> इस पेपर के लिए, लेखकों ने बाद में स्ट्रीमिंग एल्गोरिदम में उनके मूलभूत योगदान के लिए 2005 में गोडेल पुरस्कार जीता। तब से डेटा स्ट्रीमिंग एल्गोरिदम के आसपास केंद्रित काम का एक बड़ा हिस्सा रहा है जो सिद्धांत, डेटाबेस, नेटवर्किंग और प्राकृतिक भाषा प्रसंस्करण जैसे कंप्यूटर विज्ञान क्षेत्रों के विविध स्पेक्ट्रम तक फैला हुआ है।
+</ref> साथ ही 1982/83 में [[फिलिप फ्लेजोलेट]] और जी निगेल मार्टिन द्वारा भी,स्ट्रीमिंग एल्गोरिदम के क्षेत्र को सर्वप्रथम 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> स्थान में अघुलनशील होता हैं ।
 ==मॉडल==
 === डेटा स्ट्रीम मॉडल ===
-डेटा स्ट्रीम मॉडल में, कुछ या सभी इनपुट को पूर्णांकों के एक सीमित अनुक्रम (कुछ परिमित डोमेन से) के रूप में दर्शाया जाता है, जो आम तौर पर यादृच्छिक पहुंच के लिए उपलब्ध नहीं होता है, बल्कि एक स्ट्रीम में एक समय में एक आता है।<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>
 === टर्नस्टाइल और कैश रजिस्टर मॉडल ===
+अधिकांश स्ट्रीमिंग साहित्य आँकड़ों की गणना से संबंधित होता है जो संग्रहीत करने के लिए बहुत बड़े होते हैं। समस्याओं के इस वर्ग के लिए, एक सदिश <math>\mathbf{a} = (a_1, \dots, a_n)</math> (<math>\mathbf{0}</math> शून्य सदिश से प्रारंभ किया गया ) होता है जिसमें अपडेट स्ट्रीम में प्रस्तुत किया जाता है। इन एल्गोरिदम का लक्ष्य गणना करना और <math>\mathbf{a}</math> के कार्य की तुलना में अधिक कम स्थान का उपयोग करना होता है। <math>\mathbf{a}</math> प्रतिनिधित्व करने के लिए लगने वाली स्थान से अधिक कम स्थान का उपयोग कर रहा है। स्पष्ट रूप से ऐसी स्ट्रीम ओं को अद्यतन करने के लिए दो सामान्य मॉडल हैं, जिन्हें "कैश रजिस्टर" और "टर्नस्टाइल" मॉडल कहा जाता है।<ref>{{harvtxt|Gilbert|Kotidis|Muthukrishnan|Strauss|2001}}</ref>कैश रजिस्टर मॉडल में, प्रत्येक अद्यतन प्रपत्र का <math>\langle i,
+c\rangle</math> होता है, जिससे <math>a_i</math> कुछ धनात्मक से वृद्धि होती है इस प्रकार <math>c</math> पूर्णांक होता है। एक उल्लेखनीय विशेष स्थिति जब होती है तब <math>c = 1</math> होता (मात्र इकाई सम्मिलन की अनुमति होती है)।
-अधिकांश स्ट्रीमिंग साहित्य आँकड़ों की गणना से संबंधित है
+टर्नस्टाइल मॉडल में, प्रत्येक अद्यतन प्रपत्र का <math>\langle i,
-आवृत्ति वितरण जो संग्रहीत करने के लिए बहुत बड़े हैं। इस वर्ग के लिए
+c\rangle</math> होता है , जिससे <math>a_i</math> कुछ (संभवतः नकारात्मक) पूर्णांक <math>c</math> द्वारा वृद्धि की जाती है। कठोर टर्नस्टाइल मॉडल में, ननो<math>a_i</math> किसी भी समय शून्य से कम हो सकता है.
-समस्याएँ, एक वेक्टर है <math>\mathbf{a} = (a_1, \dots, a_n)</math>
-(शून्य वेक्टर से प्रारंभ किया गया <math>\mathbf{0}</math>) जिसमें अपडेट हैं
-इसे एक स्ट्रीम में प्रस्तुत किया गया। इन एल्गोरिदम का लक्ष्य गणना करना है
-के कार्य <math>\mathbf{a}</math> इसकी तुलना में काफी कम जगह का उपयोग करना
-प्रतिनिधित्व करने के लिए ले जाएगा <math>\mathbf{a}</math> एकदम सही। वहाँ दो हैं
-ऐसी धाराओं को अद्यतन करने के लिए सामान्य मॉडल, जिन्हें कैश रजिस्टर कहा जाता है और
- घूमने वाला दरवाज़ा मॉडल.<ref
-नाम = घूमने वाला दरवाज़ा >{{harvtxt|Gilbert|Kotidis|Muthukrishnan|Strauss|2001}}</ref>
-कैश रजिस्टर मॉडल में, प्रत्येक अद्यतन प्रपत्र का होता है <math>\langle i,
-c\rangle</math>, ताकि <math>a_i</math> कुछ सकारात्मकता से वृद्धि हुई है
-पूर्णांक <math>c</math>. एक उल्लेखनीय विशेष मामला है जब <math>c = 1</math>
-(केवल इकाई सम्मिलन की अनुमति है)।
-टर्नस्टाइल मॉडल में, प्रत्येक अद्यतन प्रपत्र का होता है <math>\langle i,
-c\rangle</math>, ताकि <math>a_i</math> कुछ (संभवतः नकारात्मक) पूर्णांक द्वारा वृद्धि की जाती है <math>c</math>. सख्त टर्नस्टाइल मॉडल में, नहीं
-<math>a_i</math> किसी भी समय शून्य से कम हो सकता है.
 === स्लाइडिंग विंडो मॉडल ===
-कई पेपर स्लाइडिंग विंडो मॉडल पर भी विचार करते हैं।{{Citation needed|date=November 2017}} इस मॉडल में,
+कई पेपर "स्लाइडिंग विंडो" मॉडल पर भी विचार करते हैं। इस मॉडल में, रुचि का कार्य एक निश्चित आकार की विंडो पर कंप्यूटिंग करना होता है जैसे-जैसे स्ट्रीम आगे बढ़ती है, विंडो के अंत से वस्तु विचार से हटा दिए जाते है गया जबकि स्ट्रीम से नई वस्तुएं उनका स्थान ले लेते है।
-रुचि का कार्य एक निश्चित आकार की विंडो पर कंप्यूटिंग करना है
-धारा। जैसे-जैसे स्ट्रीम आगे बढ़ती है, विंडो के अंत से आइटम आते हैं
-विचार से हटा दिया गया जबकि स्ट्रीम से नए आइटम अपना ले लिए गए
-जगह।
-उपरोक्त आवृत्ति-आधारित समस्याओं के अलावा, कुछ अन्य प्रकार की समस्याएं
+उपरोक्त आवृत्ति-आधारित समस्याओं के अतिरिक्त, कुछ अन्य प्रकार की समस्याएं का भी अध्ययन किया जाताहै। सेटिंग में कई ग्राफ़ समस्याओं का समाधान किया जाता है जहां आसन्न आव्युह या ग्राफ़ की आसन्न सूची स्ट्रीम की जाती है। समस्याएँ ऐसी भी होती हैं जो स्ट्रीम के क्रम (अर्थात, असममित कार्य) पर बहुत अधिक निर्भर होती हैं, जैसे एक स्ट्रीम में व्युत्क्रमों की संख्या और सबसे लंबे समय तक बढ़ने वाले अनुवर्ती का पता लगाना।
-का भी अध्ययन किया गया है। सेटिंग में कई ग्राफ़ समस्याओं का समाधान किया जाता है
-जहां आसन्न मैट्रिक्स या ग्राफ़ की आसन्न सूची स्ट्रीम की जाती है
-कुछ अज्ञात आदेश. कुछ समस्याएँ ऐसी भी होती हैं जो अत्यधिक निर्भर होती हैं
-धारा के क्रम पर (अर्थात, असममित कार्य), जैसे गिनती
-एक धारा में व्युत्क्रमों की संख्या और सबसे लंबे समय तक बढ़ने का पता लगाना
-परिणाम।{{citation needed|date=April 2021}}
 == मूल्यांकन ==
-{{unreferenced section|date=April 2021}}
+डेटा स्ट्रीम पर काम करने वाले एल्गोरिदम का प्रदर्शन तीन मूलभूत कारकों द्वारा मापा जाता है:
-डेटा स्ट्रीम पर काम करने वाले एल्गोरिदम का प्रदर्शन तीन बुनियादी कारकों द्वारा मापा जाता है:
+* एल्गोरिदम को स्ट्रीम के ऊपर से पारित होने की संख्या।
-* एल्गोरिदम को स्ट्रीम के ऊपर से गुजरने की संख्या।
+* उपलब्ध स्मृति।
-* उपलब्ध स्मृति.
 * एल्गोरिदम का चलने का समय।
-इन एल्गोरिदम में [[ऑनलाइन एल्गोरिदम]] के साथ कई समानताएं हैं क्योंकि इन दोनों को सभी डेटा उपलब्ध होने से पहले निर्णय लेने की आवश्यकता होती है, लेकिन वे समान नहीं हैं। डेटा स्ट्रीम एल्गोरिदम में केवल सीमित मेमोरी उपलब्ध होती है, लेकिन वे बिंदुओं के समूह के आने तक कार्रवाई को स्थगित करने में सक्षम हो सकते हैं, जबकि ऑनलाइन एल्गोरिदम को प्रत्येक बिंदु के आते ही कार्रवाई करने की आवश्यकता होती है।
+इन एल्गोरिदम में [[ऑनलाइन एल्गोरिदम]] के साथ कई समानताएं होती हैं क्योंकि इन दोनों को सभी डेटा उपलब्ध होने से पहले निर्णय लेने की आवश्यकता होती है, लेकिन वे समान नहीं होते हैं। डेटा स्ट्रीम एल्गोरिदम में मात्र सीमित मेमोरी उपलब्ध होती है, परन्तु वे बिंदुओं के समूह के आने तक संचालन को स्थगित करने में सक्षम हो सकते हैं, जबकि ऑनलाइन एल्गोरिदम को प्रत्येक बिंदु के आते ही संचालन करने की आवश्यकता होती है।
-यदि एल्गोरिदम एक सन्निकटन एल्गोरिदम है तो उत्तर की सटीकता एक अन्य महत्वपूर्ण कारक है। सटीकता को अक्सर एक के रूप में बताया जाता है <math>(\epsilon,\delta)</math> सन्निकटन का अर्थ है कि एल्गोरिदम इससे कम की त्रुटि प्राप्त करता है <math>\epsilon</math> संभाव्यता के साथ <math>1-\delta</math>.
+यदि एल्गोरिदम एक सन्निकटन एल्गोरिदम है तो उत्तर की त्रुटिहीनता एक अन्य महत्वपूर्ण कारक होता है। त्रुटिहीनता को अधिकांशतः एक के रूप में बताया जाता है <math>(\epsilon,\delta)</math> सन्निकटन का अर्थ है कि एल्गोरिदम इससे कम की त्रुटि <math>\epsilon</math> संभाव्यता के साथ <math>1-\delta</math> प्राप्त करता है।
 ==अनुप्रयोग==
-स्ट्रीमिंग एल्गोरिदम के [[ संगणक संजाल ]] में कई अनुप्रयोग हैं जैसे कि
+स्ट्रीमिंग एल्गोरिदम के [[ संगणक संजाल |नेटवर्किंग]] में कई अनुप्रयोग होते हैं जैसे कि एलीफैंट के प्रवाह के लिए नेटवर्क लिंक की जांच करना, उनकी संख्या की गिनती करना, अलग-अलग प्रवाह आकार के वितरण का अनुमान लगाना, इत्यादि।<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}}
-:<math>y = \sum_{k\geq0} \mathrm{bit}(y,k)*2^{k}</math>
-होने देना <math>\rho(y)</math> न्यूनतम की स्थिति का प्रतिनिधित्व करता है
-के बाइनरी प्रतिनिधित्व में महत्वपूर्ण 1-बिट {{mvar|y<sub>i</sub>}} के लिए एक उपयुक्त सम्मेलन के साथ <math>\rho(0)</math>.
-:<math>\rho(y)=\begin{cases}
-	\mathrm{Min}(k:\mathrm{bit}(y,k)==1) &\text{if } y>0\\
-	L &\text{if } y=0
-\end{cases}</math>
-मान लीजिए 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>\begin{array}{lll}
-E(X) &=& \sum_{i=1}^{n} \sum_{i=1}^{m_i} (j^k-(j-1)^k) \\
-&=& \frac{m}{m} [(1^k+(2^k-1^k)+\ldots+ (m_{1}^{k} - (m_{1}-1)^{k})) \\
-&&\;+\; (1^k+(2^k-1^k)+\ldots+ (m_{2}^{k} - (m_{2}-1)^{k}))+\ldots \\
-&&\;+\; (1^k+(2^k-1^k)+\ldots+ (m_{n}^{k} - (m_{n}-1)^{k}))] \\
-&=& \sum_{i=1}^{n} m_{i}^{k} = F_{k}
-\end{array}</math>
-====== की जटिलता {{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
-\frac{a_i}{m}\log{\frac{a_i}{m}}</math>, कहाँ <math>m = \sum_{i=1}^n a_i</math>.
-===ऑनलाइन शिक्षण===
-{{main|Online machine learning}}
-एक प्रशिक्षण सेट पर एक बार पास करके एक मॉडल (उदाहरण के लिए एक [[सांख्यिकीय वर्गीकरण]]) सीखें।
-* [[फ़ीचर हैशिंग]]
-* [[स्टोकेस्टिक ग्रेडिएंट डिसेंट]]
-<!--
-==निचली सीमा==
-कई डेटा स्ट्रीमिंग समस्याओं के लिए निचली सीमा की गणना की गई है
-जिसका अध्ययन किया गया है. कंप्यूटिंग के लिए अब तक की सबसे आम तकनीक
-ये निचली सीमाएँ [[संचार जटिलता]] का उपयोग कर रही हैं।{{citation needed|date=April 2021}}
-== यह भी देखें ==
-* [[डेटा स्ट्रीम खनन]]
-* [[डेटा स्ट्रीम क्लस्टरिंग]]
-* [[ऑनलाइन एल्गोरिदम]]
-* [[स्ट्रीम प्रोसेसिंग]]
-* [[अनुक्रमिक एल्गोरिथ्म]]
-==टिप्पणियाँ==
-<references/>
-==संदर्भ==
-* {{citation
-  | title = The space complexity of approximating the frequency moments
-  | last1=Alon | first1=Noga | author1-link = Noga Alon
-  | last2=Matias | first2=Yossi | author2-link = Yossi Matias
-  | last3=Szegedy | first3=Mario | author3-link = Mario Szegedy
-  | year = 1999
-  | doi=10.1006/jcss.1997.1545
-  | journal = [[Journal of Computer and System Sciences]]
-  | volume = 58
-  | issue = 1
-  | issn = 0022-0000
-  | pages = 137&ndash;147| doi-access = free
-  }}. First published as {{citation
-  | contribution = The space complexity of approximating the frequency moments
-  | last1=Alon | first1=Noga
-  | last2=Matias | first2=Yossi
-  | last3=Szegedy | first3=Mario
-  | doi=10.1145/237814.237823
-  | year = 1996
-  | title = Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996)
-  | isbn = 978-0-89791-785-8
-  | pages = 20&ndash;29| title-link=Symposium on Theory of Computing | citeseerx=10.1.1.131.4984 | s2cid=1627911 }}.
-* {{citation
-  | contribution = Models and issues in data stream systems
-  | last1 = Babcock | first1=Brian
-  | last2 = Babu | first2=Shivnath
-  | last3 = Datar | first3= Mayur
-  | last4 = Motwani | first4=Rajeev | author4-link = Rajeev Motwani
-  | last5 = Widom | first5=Jennifer | author5-link = Jennifer Widom
-  | url = http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf
-  | doi = 10.1145/543613.543615 | pages = 1–16
-  | title= Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002)
-  | year = 2002| isbn = 978-1581135077 | citeseerx = 10.1.1.138.190 | s2cid = 2071130 }}.
-* {{citation
-  | title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
-  | last1=Gilbert|first1=A. C. |author1-link= Anna C. Gilbert
-  | last2=Kotidis|first2=Y.
-  | last3=Muthukrishnan|first3=S. |author3-link=S. Muthukrishnan (computer scientist)
-  | last4=Strauss|first4=M. J.
-  | url = http://www.vldb.org/conf/2001/P079.pdf
-  | journal = Proceedings of the International Conference on Very Large Data Bases
-  | pages = 79&ndash;88
-  | year = 2001}}.
-* {{cite conference | last1 = Kane | first1 = Daniel M.
- | last2 = Nelson | first2 = Jelani
- | last3 = Woodruff | first3 = David P.
- | chapter = An optimal algorithm for the distinct elements problem
- | title = Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
- | series = PODS '10
- | year = 2010
- | isbn = 978-1-4503-0033-9
- | pages = 41&ndash;52
- | doi = 10.1145/1807085.1807094
- | publisher = ACM
- | location = New York, NY, USA
-| citeseerx = 10.1.1.164.142
- | s2cid = 10006932
- }}.
-* {{citation
-  | title = A simple algorithm for finding frequent elements in streams and bags
-  | last1=Karp|first1=R. M. | author1-link = Richard Karp
-  | last2=Papadimitriou|first2=C. H. | author2-link = Christos Papadimitriou
-  | last3=Shenker|first3=S. | author3-link = Scott Shenker
-  | year = 2003
-  | volume = 28 | issue = 1 | pages = 51–55 | doi = 10.1145/762471.762473
-  | journal = ACM Transactions on Database Systems| citeseerx=10.1.1.116.8530| s2cid=952840}}.
-* {{citation
- |contribution = Data streaming algorithms for estimating entropy of network traffic
- |last1        = Lall
- |first1       = Ashwin
- |last2        = Sekar
- |first2       = Vyas
- |last3        = Ogihara
- |first3       = Mitsunori
- |last4        = Xu
- |first4       = Jun
- |last5        = Zhang
- |first5       = Hui
- |title        = Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006)
- |pages        = 145
- |doi          = 10.1145/1140277.1140295
- |url          = ftp://ftp.cs.rochester.edu/pub/papers/theory/05.tr886.Data_streamg_algms_for_estimating_entropy_of_network_traffic.pdf
- |year         = 2006
-|isbn        = 978-1595933195
- |hdl        = 1802/2537
- |s2cid = 240982
- |hdl-access= free
- }}{{Dead link|date=June 2018 |bot=InternetArchiveBot |fix-attempted=no }}.
-* {{citation
-  | title = A Tutorial on Network Data Streaming
-  | last1 = Xu | first1=Jun (Jim)
-  | url = http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf
-  | year = 2007}}.
-* Heath, D., Kasif, S., Kosaraju, R., Salzberg, S.,  Sullivan, G., "Learning Nested Concepts With Limited Storage",  Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777–782,  Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1991
-* {{citation
-  | title = Counting large numbers of events in small registers
-  | last1 = Morris | first1 = Robert
-  | year = 1978
-  | volume = 21 | issue = 10 | pages = 840–842 | doi = 10.1145/359619.359627
-  | journal = Communications of the ACM| s2cid = 36226357 }}.
-{{Algorithmic paradigms}}
-[[Category: स्ट्रीमिंग एल्गोरिदम]]
+.
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category:Created On 07/07/2023]]
+[[Category:Harv and Sfn no-target errors]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with reference errors]]
+[[Category:Templates Vigyan Ready]]

Anonymous

Search

स्ट्रीमिंग एल्गोरिदम: Difference between revisions

Latest revision as of 10:17, 2 August 2023

इतिहास

मॉडल

डेटा स्ट्रीम मॉडल

टर्नस्टाइल और कैश रजिस्टर मॉडल

स्लाइडिंग विंडो मॉडल

मूल्यांकन

अनुप्रयोग

Navigation

Wiki tools

Page tools

Other projects

Hidden categories