STREAM k-मेडियन्स समस्या के लिए विकसित एक एकल-पास, स्थिर-तत्व सन्निकटन एल्गोरिदम है। k-मेडियन्स समस्या N डेटा बिंदुओं को k क्लस्टर्स या समूहों में क्लस्टर करना है ताकि बिंदुओं और उस क्लस्टर केंद्र के बीच वर्ग त्रुटि का योग (SSQ) न्यूनतम हो जिसे उन्हें सौंपा गया है। विचार समान बिंदुओं को उसी क्लस्टर में असाइन करना है, जहां ये बिंदु अन्य क्लस्टर्स में बिंदुओं से असमान हैं।
स्ट्रीम डेटा मॉडल में, डेटा बिंदुओं को केवल एक बार देखा जा सकता है, और मेमोरी और समय सीमित हैं। उच्च-गुणवत्ता वाली क्लस्टरिंग लागू करने के लिए, STREAM एल्गोरिदम m बिंदुओं के बकेट्स (या बैच) में डेटा स्ट्रीम को संसाधित करता है, प्रत्येक बकेट मुख्य मेमोरी में फिट होता है।
प्रत्येक बकेट, bi, के लिए, STREAM बकेट के बिंदुओं को k क्लस्टर्स में क्लस्टर करता है। यह तब बकेट जानकारी को सारांशित करता है केवल k केंद्रों के बारे में जानकारी रखकर, प्रत्येक क्लस्टर केंद्र को उसके क्लस्टर को सौंपे गए बिंदुओं की संख्या से भारित करके।
STREAM फिर बिंदुओं को त्याग देता है, केवल केंद्र जानकारी रखता है। क्योंकि पर्याप्त केंद्र एकत्र किए गए हैं, भारित केंद्रों को O(k) क्लस्टर केंद्रों का एक और समूह बनाने के लिए क्लस्टर किया जाता है। इसे दोहराया जाता है ताकि प्रत्येक स्तर पर, अधिकतम m बिंदु रखे जाएं। यह दृष्टिकोण डेटा स्ट्रीम k-मेडियन्स के लिए एक-पास, O(kN)-समय, O(Nε)-स्पेस (किसी स्थिर ε < 1 के लिए), स्थिर-गुणक सन्निकटन एल्गोरिदम में परिणाम देता है।
STREAM निश्चित स्थान और समय के साथ गुणवत्ता k-मेडियन्स क्लस्टर्स को बदलता है। हालांकि, यह न तो रिकॉर्ड के विकास और न ही समय दानेदारता को मानता है। क्लस्टरिंग स्ट्रीम के पुराने, पुराने डेटा द्वारा प्रभुत्वित हो सकती है। क्लस्टर्स की विशेषता उस क्षण के साथ भिन्न हो सकती है जिस पर उनका मूल्यांकन किया जाता है, और समय क्षितिज जिस पर वे मापे जाते हैं।
उदाहरण के लिए, एक उपयोगकर्ता पिछले सप्ताह, पिछले महीने, या पिछले साल दिखाई देने वाले क्लस्टर्स की जांच करना चाह सकता है। ये अलग हो सकते हैं। इसलिए, एक डेटा स्ट्रीम क्लस्टरिंग एल्गोरिदम को उपयोगकर्ता-निर्दिष्ट समय अवधि में इंटरैक्टिव तरीके से क्लस्टर्स की गणना करने के लिए लचीलेपन का भी समर्थन करना चाहिए।
CluStream उपयोगकर्ता-निर्दिष्ट, ऑनलाइन क्लस्टरिंग क्वेरी के आधार पर विकसित डेटा स्ट्रीम के क्लस्टरिंग के लिए एक एल्गोरिदम है। यह क्लस्टरिंग प्रक्रिया को ऑनलाइन और ऑफलाइन घटकों में विभाजित करता है।
ऑनलाइन घटक माइक्रो-क्लस्टर्स का उपयोग करके डेटा स्ट्रीम के बारे में सारांश सांख्यिकी की गणना और संग्रह करता है, और माइक्रो-क्लस्टर्स की वृद्धिशील ऑनलाइन गणना और रखरखाव करता है। ऑफलाइन घटक मैक्रो-क्लस्टरिंग करता है और झुके हुए समय फ्रेम मॉडल पर निर्भर सहेजे गए सारांश सांख्यिकी का उपयोग करके कई उपयोगकर्ता प्रश्नों को हल करता है।
ऐतिहासिक और वर्तमान स्ट्रीम डेटा जानकारी दोनों के आधार पर विकसित डेटा स्ट्रीम को क्लस्टर करने के लिए, झुका हुआ समय फ्रेम मॉडल (जैसे प्रगतिशील लॉगरिदमिक मॉडल) अपनाया जाता है, जो हाल ही के आधार पर विभिन्न दानेदारता स्तरों पर माइक्रो-क्लस्टर्स के एक सेट के स्नैपशॉट संग्रहीत करता है।
