यादृच्छिक एल्गोरिदम - यादृच्छिक नमूनाकरण और ब्लूप्रिंट के रूप में यादृच्छिक एल्गोरिदम, बड़े, उच्च-आयामी डेटा स्ट्रीम से निपटने के लिए उपयोग किए जाते हैं। यादृच्छिकीकरण की आवश्यकता ज्ञात निश्चित एल्गोरिदम की तुलना में सरल और अधिक प्रभावी एल्गोरिदम की ओर ले जाती है।
यदि एक यादृच्छिक एल्गोरिदम लगातार सही उत्तर देता है लेकिन चलने का समय बदलता है, तो इसे लास वेगास एल्गोरिदम कहा जाता है। इसके विपरीत, एक मोंटे कार्लो एल्गोरिदम में चलने के समय पर सीमाएं होती हैं लेकिन सच्चा परिणाम बहाल नहीं कर सकता। आमतौर पर मोंटे कार्लो एल्गोरिदम पर विचार किया जाता है। यादृच्छिक एल्गोरिदम का महत्व केवल निर्धारित एल्गोरिदम के एक समूह पर एक संभावना वितरण के रूप में है।
यह देखते हुए कि एक यादृच्छिक एल्गोरिदम परिणाम के रूप में एक यादृच्छिक चर को पुनर्स्थापित करता है, उस यादृच्छिक चर की पूंछ संभावना पर सीमाएं रखना संभव है। यह हमें बताता है कि एक यादृच्छिक चर के अपने अपेक्षित मूल्य से भिन्न होने की संभावना कम है। मुख्य उपकरण चेबीशेव की असमानता है।
मान लीजिए X माध्य μ और मानक विचलन σ (विचरण σ2) के साथ एक यादृच्छिक चर है। चेबीशेव की असमानता कहती है कि
$$\mathrm{P(|X-\mu|>k)<\frac{\sigma^2 }{k^2}}$$
किसी भी दिए गए सकारात्मक वास्तविक संख्या, k के लिए। इस असमानता का उपयोग एक यादृच्छिक चर के विचरण को सीमित करने के लिए किया जाता है। कई मामलों में, कई यादृच्छिक चरों का उपयोग इस परिणाम में विश्वास को सुधारने के लिए किया जा सकता है। इन यादृच्छिक चरों को पूरी तरह से स्वतंत्र मानते हुए, चेरनॉफ सीमाओं का उपयोग किया जा सकता है।
मान लीजिए X1X2 … Xn स्वतंत्र पॉइसन परीक्षण हैं। एक पॉइसन परीक्षण में, सफलता की संभावना परीक्षण से परीक्षण में बदलती है। यदि X, X1 से Xn का योग है, तो चेरनॉफ सीमा का एक कमजोर संस्करण हमें बताता है कि
$$\mathrm{P[X<(1+\delta)\mu]< e^{-\mu\delta^2}}$$
जहां δ ∈ (0, 1]। यह दर्शाता है कि संभावना घातीय रूप से कम हो जाती है जैसे-जैसे यह माध्य से दूर जाता है, जो खराब अनुमानों को बहुत अधिक असंभव बनाता है।
डेटा स्ट्रीम प्रबंधन प्रणाली - एक डेटा स्ट्रीम प्रबंधन प्रणाली में, कई डेटा स्ट्रीम हैं। वे ऑनलाइन दिखाई देते हैं और निरंतर, अस्थायी श्रृंखला, और संभावित रूप से अनंत हैं। क्योंकि एक डेटा स्ट्रीम से एक घटक संसाधित किया गया है, इसे त्याग दिया जाता है या संग्रहीत किया जाता है, और इसे स्पष्ट रूप से मेमोरी में सहेजे बिना आसानी से प्राप्त नहीं किया जा सकता।
एक स्ट्रीम डेटा क्वेरी प्रसंस्करण संरचना में तीन तत्व शामिल हैं जैसे एंड-यूज़र, क्वेरी प्रोसेसर, और स्क्रैच स्पेस (जिसमें मुख्य मेमोरी और डिस्क शामिल हो सकते हैं)। एक एंड यूज़र DSMS को एक क्वेरी देता है, और क्वेरी प्रोसेसर क्वेरी लेता है, स्क्रैच स्पेस में सहेजे गए डेटा का उपयोग करके इसे संसाधित करता है, और परिणामों को उपयोगकर्ता को पुनर्स्थापित करता है।
क्वेरीज़ एक-बार क्वेरी या निरंतर क्वेरी हो सकती हैं। एक-बार क्वेरी को डेटा सेट के एक पॉइंट-इन-टाइम फोटोग्राफ पर एक बार गणना की जाती है, उत्तर उपयोगकर्ता को बहाल किया जाता है। एक निरंतर क्वेरी की गणना लगातार की जाती है जैसे-जैसे डेटा स्ट्रीम आना जारी रहती है।
