मूल अवधारणा
डेटा प्रोसेसिंग के मामले में, R*-trees को स्थानिक जानकारी को अनुक्रमित करने के लिए लागू किए गए R-trees के एक प्रकार के रूप में परिभाषित किया गया है।
R*-ट्री की निर्माण लागत मानक R-पेड़ों की तुलना में थोड़ी अधिक होती है, क्योंकि डेटा को फिर से डालने की आवश्यकता हो सकती है; लेकिन परिणामी पेड़ में आम तौर पर बेहतर क्वेरी प्रदर्शन होगा। मानक आर-पेड़ के समान, यह बिंदु और स्थानिक डेटा दोनों को स्टोर कर सकता है। 1990 में नॉरबर्ट बेकमैन, हैंस-पीटर क्रिगल, राल्फ श्नाइडर और बर्नहार्ड सीगर द्वारा R*-ट्री की अवधारणा प्रस्तावित की गई थी।
R*-पेड़ों और R-पेड़ों के बीच अंतर
R*-Tree बार-बार डालने से बनता है। इस पेड़ में बहुत कम (यानी लगभग नहीं) ओवरलैप है, जिसके परिणामस्वरूप अच्छा क्वेरी प्रदर्शन होता है। आर-पेड़ों के प्रदर्शन के लिए कवरेज और ओवरलैप दोनों को कम करना बहुत महत्वपूर्ण है। डेटा सम्मिलन या क्वेरी पर ओवरलैप का अर्थ यह है कि पेड़ की एक से अधिक शाखाओं का विस्तार करने की आवश्यकता होती है (जिस तरह से डेटा को उन क्षेत्रों में विभाजित किया जा रहा है जो ओवरलैप हो सकते हैं)। एक न्यूनतम कवरेज प्रूनिंग प्रदर्शन को बढ़ाता है, विशेष रूप से नकारात्मक श्रेणी प्रश्नों के लिए पूरे पृष्ठों को बार-बार खोज से बाहर करने की अनुमति देता है। R*-tree दोनों को कम करने का प्रयास करता है, एक संशोधित नोड स्प्लिट एल्गोरिथम के संग्रह को लागू करता है और नोड ओवरफ्लो पर जबरन पुनर्निवेश की अवधारणा को लागू करता है। यह अवधारणा इस अवलोकन पर आधारित है कि आर-पेड़ संरचनाएं उस क्रम के लिए अतिसंवेदनशील होती हैं जिसमें उनकी प्रविष्टियां डाली जाती हैं, इसलिए एक सम्मिलन-निर्मित (बल्क-लोडेड के बजाय) संरचना उप-इष्टतम होने की संभावना है। प्रविष्टियों को हटाने और पुन:सम्मिलित करने से उन्हें पेड़ में ऐसी जगह "ढूंढने" की अनुमति मिलती है जो उनके वास्तविक स्थान से अधिक उपयुक्त हो सकती है।
एल्गोरिदम और जटिलता
- R*-tree क्वेरी और डिलीट ऑपरेशंस के लिए नियमित R-ट्री के समान एल्गोरिदम लागू करता है।
- सम्मिलित करते समय, R*-tree एक संयुक्त रणनीति लागू करता है। लीफ नोड्स के लिए, ओवरलैप को न्यूनतम किया जाता है, जबकि आंतरिक नोड्स के लिए, इज़ाफ़ा और क्षेत्र को न्यूनतम किया जाता है।
- विभाजन के समय, R*-ट्री एक टोपोलॉजिकल स्प्लिट लागू करता है जो परिधि के आधार पर विभाजित अक्ष का चयन करता है, फिर ओवरलैप को कम करता है।
- बढ़ी हुई विभाजन रणनीति के अलावा, आर*-ट्री बी-ट्री को संतुलित करने की अवधारणा से प्रेरित होकर पेड़ में वस्तुओं और उप-वृक्षों को पुन:सम्मिलित करके विभाजन को छोड़ने की भी कोशिश करता है।
सबसे खराब स्थिति की क्वेरी और हटाने की जटिलता इस प्रकार आर-ट्री के समान है। R*-tree में सम्मिलन रणनीति O(M log M) के साथ R-पेड़ की रैखिक विभाजन रणनीति (O(M)) की तुलना में अधिक जटिल है, लेकिन द्विघात विभाजन रणनीति (O(M