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

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

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

इतिहास

यघपि स्ट्रीमिंग एल्गोरिदम का अध्ययन मुनरो और पैटरसन द्वारा 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$ प्राप्त करता है।

अनुप्रयोग

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

.