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

Revision as of 12:20, 20 July 2023

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

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

इतिहास

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

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

मॉडल

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

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

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

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

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

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

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

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

मूल्यांकन

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

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

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

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

अनुप्रयोग

स्ट्रीमिंग एल्गोरिदम के नेटवर्किंग में कई अनुप्रयोग होते हैं जैसे कि एलीफैंट के प्रवाह के लिए नेटवर्क लिंक की जांच करना, उनकी संख्या की गिनती करना, अलग-अलग प्रवाह आकार के वितरण का अनुमान लगाना, इत्यादि।^[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
↑ 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.

[:0-2] Cite error: Invalid <ref> tag; no text was provided for refs named :0

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

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

[5] 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)

[6] 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)

[7] Gilbert et al. (2001)

[8] Xu (2007)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ 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 में [[फिलिप फ्लेजोलेट]] और जी निगेल मार्टिन द्वारा भी,<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> स्थान में अघुलनशील होता हैं ।
 ==मॉडल==
 === डेटा स्ट्रीम मॉडल ===
-डेटा स्ट्रीम मॉडल में, कुछ या सभी इनपुट को पूर्णांकों के एक सीमित अनुक्रम (कुछ परिमित डोमेन से) के रूप में दर्शाया जाता है, जो आम तौर पर यादृच्छिक पहुंच के लिए उपलब्ध नहीं होता है, बल्कि एक स्ट्रीम में एक समय में एक आता है।<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>\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,
+टर्नस्टाइल मॉडल में, प्रत्येक अद्यतन प्रपत्र का <math>\langle i,
-c\rangle</math>, ताकि <math>a_i</math> कुछ सकारात्मकता से वृद्धि हुई है
+c\rangle</math> होता है , जिससे <math>a_i</math> कुछ (संभवतः नकारात्मक) पूर्णांक <math>c</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>(\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> उनके पास एप्लिकेशन भी हैं
-डेटाबेस, जैसे जॉइन के आकार का अनुमान लगाना (एसक्यूएल)
 .

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 12:20, 20 July 2023

Contents

इतिहास

मॉडल

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

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

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

मूल्यांकन

अनुप्रयोग

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 12:20, 20 July 2023

इतिहास

मॉडल

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

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

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

मूल्यांकन

अनुप्रयोग

Navigation

Wiki tools

Page tools

Other projects

Hidden categories