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

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

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

इतिहास

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

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

मॉडल

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

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

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

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

घूमने वाला दरवाज़ा मॉडल.

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

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

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

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

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

मूल्यांकन

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

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

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

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

अनुप्रयोग

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