यूबी-ट्री: Difference between revisions
From Vigyanwiki
(Created page with "{{Infobox data structure | name = UB-tree | image = Z-curve45.svg | alt = | caption = Two dimensional Z-order | type...") |
No edit summary |
||
| Line 26: | Line 26: | ||
| merge_worst = | | merge_worst = | ||
}} | }} | ||
[[रूडोल्फ बायर]] और [[वोल्कर मार्कल]] द्वारा प्रस्तावित यूबी-ट्री [[बहुआयामी डेटा]] को संग्रहीत करने और कुशलतापूर्वक पुनर्प्राप्त करने के लिए एक संतुलित पेड़ है। यह मूल रूप से एक B+ पेड़ है (जानकारी केवल पत्तियों में) जिसमें रिकॉर्ड Z-ऑर्डर (वक्र) | [[रूडोल्फ बायर]] और [[वोल्कर मार्कल]] द्वारा प्रस्तावित '''यूबी-ट्री''' [[बहुआयामी डेटा]] को संग्रहीत करने और कुशलतापूर्वक पुनर्प्राप्त करने के लिए एक संतुलित पेड़ है। यह मूल रूप से एक B+ पेड़ है (जानकारी केवल पत्तियों में) जिसमें रिकॉर्ड Z-ऑर्डर (वक्र) के अनुसार संग्रहीत होते हैं, जिन्हें मॉर्टन ऑर्डर भी कहा जाता है। Z-ऑर्डर की गणना केवल कुंजियों को बिटवाइज़ इंटरलेसिंग करके की जाती है। | ||
सम्मिलन, विलोपन और बिंदु क्वेरी सामान्य B+ | सम्मिलन, विलोपन और बिंदु क्वेरी सामान्य B+ ट्री की तरह ही की जाती है। चूँकि बहुआयामी बिंदु डेटा में श्रेणी खोज करने के लिए डेटा बेस में सामने आए एक बिंदु से, अगले Z-मान की गणना करने के लिए एक एल्गोरिदम प्रदान किया जाना चाहिए जो बहुआयामी खोज सीमा में है। | ||
इस मुख्य समस्या को हल करने के लिए मूल एल्गोरिदम आयामीता के साथ घातीय था और इसलिए संभव नहीं था<ref>{{cite citeseerx |first=V. |last=Markl |title=MISTRAL: Processing Relational Queries using a Multidimensional Access Technique |year=1999 |citeseerx=10.1.1.32.6487 }}</ref> ( | इस मुख्य समस्या को हल करने के लिए मूल एल्गोरिदम आयामीता के साथ घातीय था और इसलिए वह संभव नहीं था<ref>{{cite citeseerx |first=V. |last=Markl |title=MISTRAL: Processing Relational Queries using a Multidimensional Access Technique |year=1999 |citeseerx=10.1.1.32.6487 }}</ref> ( गेटनेक्स्टज़-एड्रेस ). ज़ेड-एड्रेस बिट लंबाई के साथ यूबी-ट्री रेंज क्वेरी लीनियर के इस महत्वपूर्ण भाग का समाधान बाद में वर्णित किया गया है।<ref>{{cite conference |first1=Frank |last1=Ramsak |first2=Volker |last2=Markl |first3=Robert |last3=Fenk |first4=Martin |last4=Zirkel |first5=Klaus |last5=Elhardt |first6=Rudolf |last6=Bayer |title=यूबी-ट्री को डेटाबेस सिस्टम कर्नेल में एकीकृत करना|conference=26th International Conference on Very Large Data Bases |conference-url=http://www.vldb.org/archives/website/2000/ |date=September 10–14, 2000 |pages=263–272 |url=http://www.vldb.org/conf/2000/P263.pdf}}</ref> इस विधि का वर्णन पहले ही एक पुराने पेपर में किया जा चुका है<ref>{{cite journal |url=http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf |first1=H. |last1=Tropf |first2=H. |last2=Herzog |title=गतिशील रूप से संतुलित पेड़ों में बहुआयामी रेंज खोज|journal=Angewandte Informatik (Applied Informatics) |issue=2/1981 |pages=71–77 |issn=0013-5704}}</ref> जहां खोज वृक्षों के साथ Z-ऑर्डर का उपयोग पहली बार प्रस्तावित किया गया है। | ||
==संदर्भ== | ==संदर्भ == | ||
<references/> | <references/> | ||
Revision as of 15:03, 16 July 2023
| UB-tree | ||||
|---|---|---|---|---|
 Two dimensional Z-order | ||||
| Type | tree | |||
| Invented by | Rudolf Bayer and Volker Markl | |||
| Time complexity in big O notation | ||||
| ||||
रूडोल्फ बायर और वोल्कर मार्कल द्वारा प्रस्तावित यूबी-ट्री बहुआयामी डेटा को संग्रहीत करने और कुशलतापूर्वक पुनर्प्राप्त करने के लिए एक संतुलित पेड़ है। यह मूल रूप से एक B+ पेड़ है (जानकारी केवल पत्तियों में) जिसमें रिकॉर्ड Z-ऑर्डर (वक्र) के अनुसार संग्रहीत होते हैं, जिन्हें मॉर्टन ऑर्डर भी कहा जाता है। Z-ऑर्डर की गणना केवल कुंजियों को बिटवाइज़ इंटरलेसिंग करके की जाती है।
सम्मिलन, विलोपन और बिंदु क्वेरी सामान्य B+ ट्री की तरह ही की जाती है। चूँकि बहुआयामी बिंदु डेटा में श्रेणी खोज करने के लिए डेटा बेस में सामने आए एक बिंदु से, अगले Z-मान की गणना करने के लिए एक एल्गोरिदम प्रदान किया जाना चाहिए जो बहुआयामी खोज सीमा में है।
इस मुख्य समस्या को हल करने के लिए मूल एल्गोरिदम आयामीता के साथ घातीय था और इसलिए वह संभव नहीं था[1] ( गेटनेक्स्टज़-एड्रेस ). ज़ेड-एड्रेस बिट लंबाई के साथ यूबी-ट्री रेंज क्वेरी लीनियर के इस महत्वपूर्ण भाग का समाधान बाद में वर्णित किया गया है।[2] इस विधि का वर्णन पहले ही एक पुराने पेपर में किया जा चुका है[3] जहां खोज वृक्षों के साथ Z-ऑर्डर का उपयोग पहली बार प्रस्तावित किया गया है।
संदर्भ
- ↑ Markl, V. (1999). "MISTRAL: Processing Relational Queries using a Multidimensional Access Technique". CiteSeerX 10.1.1.32.6487.
- ↑ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (September 10–14, 2000). यूबी-ट्री को डेटाबेस सिस्टम कर्नेल में एकीकृत करना (PDF). 26th International Conference on Very Large Data Bases. pp. 263–272.
- ↑ Tropf, H.; Herzog, H. "गतिशील रूप से संतुलित पेड़ों में बहुआयामी रेंज खोज" (PDF). Angewandte Informatik (Applied Informatics) (2/1981): 71–77. ISSN 0013-5704.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
