आर-ट्री: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 17: Line 17:
}}
}}
[[Image:R-tree.svg|thumb|400px|right|2डी आयतों के लिए आर-ट्री का सरल उदाहरण]]
[[Image:R-tree.svg|thumb|400px|right|2डी आयतों के लिए आर-ट्री का सरल उदाहरण]]
[[Image:RTree-Visualization-3D.svg|thumb|400px|right|[[ELKI]] का उपयोग करके 3D बिंदुओं के लिए R*-ट्री का विज़ुअलाइज़ेशन (क्यूब्स निर्देशिका पृष्ठ हैं)]]'''आर-ट्री''' ट्री डेटा संरचनाएं हैं जिनका उपयोग [[स्थानिक सूचकांक]] के लिए किया जाता है, अर्थात, [[भौगोलिक समन्वय प्रणाली]], [[आयत]] या [[बहुभुज]] जैसी बहु-आयामी जानकारी को अनुक्रमित करने के लिए आर-ट्री का प्रस्ताव 1984 में एंटोनिन गुटमैन द्वारा किया गया था<ref name="guttman">{{Cite book | last1 = Guttman | first1 = A. | chapter = R-Trees: A Dynamic Index Structure for Spatial Searching| doi = 10.1145/602259.602266 | title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84 | pages = 47 | year = 1984 | isbn = 978-0897911283 | s2cid = 876601 | chapter-url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref> और इसे सैद्धांतिक और व्यावहारिक दोनों संदर्भों में महत्वपूर्ण उपयोग मिला है।<ref name="rtree-book">{{cite book|author1=Y. Manolopoulos|author2=A. Nanopoulos|author3=Y. Theodoridis|title=R-Trees: Theory and Applications|url=https://books.google.com/books?id=1mu099DN9UwC&pg=PR5|access-date=8 October 2011|year=2006|publisher=Springer|isbn=978-1-85233-977-7}}</ref> आर-ट्री के लिए एक सामान्य वास्तविक दुनिया का उपयोग स्थानिक वस्तुओं जैसे कि रेस्तरां स्थानों या बहुभुजों को संग्रहीत करना हो सकता है, जिनसे विशिष्ट मानचित्र बने होते हैं: सड़कें, इमारतें, झीलों की रूपरेखा, समुद्र तट, आदि और फिर प्रश्नों के तुरंत उत्तर खोजे जाते है जैसे कि मेरे वर्तमान स्थान के 2 किमी के अंदर सभी संग्रहालय खोजे, मेरे स्थान के 2 किमी के अंदर सभी सड़क खंडों को पुनः प्राप्त करें (उन्हें [[ नेविगेशन प्रणाली |नेविगेशन प्रणाली]] में प्रदर्शित करने के लिए) या निकटतम गैस स्टेशन खोजे जाते है (चूँकि सड़कों को ध्यान में नहीं रखते हुए) आर-ट्री ग्रेट-सर्कल दूरी सहित विभिन्न दूरी आव्यूह के लिए निकटतम समीप खोज<ref name="geodetic">{{Cite conference | doi = 10.1007/978-3-642-40235-7_9| chapter = Geodetic Distance Queries on R-Trees for Indexing Geographic Data| title = स्थानिक और लौकिक डेटाबेस में प्रगति| volume = 8098| pages = 146| series = Lecture Notes in Computer Science| year = 2013| last1 = Schubert | first1 = E. | last2 = Zimek | first2 = A. | last3 = Kriegel | first3 = H. P. | author-link3=Hans-Peter Kriegel| isbn = 978-3-642-40234-0}}</ref> को भी तेज कर सकता है।<ref>{{Cite conference | doi = 10.1145/223784.223794| chapter = Nearest neighbor queries| title = Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95| pages = 71| year = 1995| last1 = Roussopoulos | first1 = N. | last2 = Kelley | first2 = S. | last3 = Vincent | first3 = F. D. R. | isbn = 0897917316| doi-access = free}}</ref>  
[[Image:RTree-Visualization-3D.svg|thumb|400px|right|[[ELKI]] का उपयोग करके 3D बिंदुओं के लिए R*-ट्री का विज़ुअलाइज़ेशन (क्यूब्स निर्देशिका पृष्ठ हैं)]]'''आर-ट्री''' ट्री डेटा संरचनाएं हैं जिनका उपयोग [[स्थानिक सूचकांक]] के लिए किया जाता है, अर्थात, [[भौगोलिक समन्वय प्रणाली]], [[आयत]] या [[बहुभुज]] जैसी बहु-आयामी जानकारी को अनुक्रमित करने के लिए आर-ट्री का प्रस्ताव 1984 में एंटोनिन गुटमैन द्वारा किया गया था<ref name="guttman">{{Cite book | last1 = Guttman | first1 = A. | chapter = R-Trees: A Dynamic Index Structure for Spatial Searching| doi = 10.1145/602259.602266 | title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84 | pages = 47 | year = 1984 | isbn = 978-0897911283 | s2cid = 876601 | chapter-url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref> और इसे सैद्धांतिक और व्यावहारिक दोनों संदर्भों में महत्वपूर्ण उपयोग मिला है।<ref name="rtree-book">{{cite book|author1=Y. Manolopoulos|author2=A. Nanopoulos|author3=Y. Theodoridis|title=R-Trees: Theory and Applications|url=https://books.google.com/books?id=1mu099DN9UwC&pg=PR5|access-date=8 October 2011|year=2006|publisher=Springer|isbn=978-1-85233-977-7}}</ref> आर-ट्री के लिए एक सामान्य वास्तविक दुनिया का उपयोग स्थानिक वस्तुओं जैसे कि रेस्तरां स्थानों या बहुभुजों को संग्रहीत करना हो सकता है, जिनसे विशिष्ट मानचित्र बने होते हैं: सड़कें, इमारतें, झीलों की रूपरेखा, समुद्र तट, आदि और फिर प्रश्नों के तुरंत उत्तर खोजे जाते है जैसे कि मेरे वर्तमान स्थान के 2 किमी के अंदर सभी संग्रहालय खोजे, मेरे स्थान के 2 किमी के अंदर सभी सड़क खंडों को पुनः प्राप्त करें (उन्हें [[ नेविगेशन प्रणाली |नेविगेशन प्रणाली]] में प्रदर्शित करने के लिए) या निकटतम गैस स्टेशन खोजे जाते है (चूँकि सड़कों को ध्यान में नहीं रखते हुए) आर-ट्री ग्रेट-सर्कल दूरी सहित विभिन्न दूरी आव्यूह के लिए निकटतम समीप खोज<ref name="geodetic">{{Cite conference | doi = 10.1007/978-3-642-40235-7_9| chapter = Geodetic Distance Queries on R-Trees for Indexing Geographic Data| title = स्थानिक और लौकिक डेटाबेस में प्रगति| volume = 8098| pages = 146| series = Lecture Notes in Computer Science| year = 2013| last1 = Schubert | first1 = E. | last2 = Zimek | first2 = A. | last3 = Kriegel | first3 = H. P. | author-link3=Hans-Peter Kriegel| isbn = 978-3-642-40234-0}}</ref> को भी तेज कर सकता है।<ref>{{Cite conference | doi = 10.1145/223784.223794| chapter = Nearest neighbor queries| title = Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95| pages = 71| year = 1995| last1 = Roussopoulos | first1 = N. | last2 = Kelley | first2 = S. | last3 = Vincent | first3 = F. D. R. | isbn = 0897917316| doi-access = free}}</ref>  




== आर-ट्री विचार ==
== आर-ट्री विचार                                 ==


डेटा संरचना का मुख्य विचार आस-पास की वस्तुओं को समूहित करना और उन्हें ट्री के अगले उच्च स्तर में उनकी न्यूनतम सीमा वाली आयत के साथ प्रस्तुत करना है; आर-ट्री में आर आयत के लिए है। चूँकि सभी वस्तुएँ इस बाउंडिंग आयत के अंदर स्थित हैं, एक क्वेरी जो बाउंडिंग आयत को प्रतिच्छेद नहीं करती है, वह किसी भी निहित वस्तु को प्रतिच्छेद नहीं कर सकती है। पत्ती स्तर पर, प्रत्येक आयत एक एकल वस्तु का वर्णन करता है; उच्च स्तर पर एकत्रीकरण में वस्तुओं की बढ़ती संख्या सम्मिलित होती है। इसे डेटा सेट के तेजी से सामान्य अनुमान के रूप में भी देखा जा सकता है।
डेटा संरचना का मुख्य विचार आस-पास की वस्तुओं को समूहित करना और उन्हें ट्री के अगले उच्च स्तर में उनकी न्यूनतम सीमा वाली आयत के साथ प्रस्तुत करना है; आर-ट्री में आर आयत के लिए है। चूँकि सभी वस्तुएँ इस बाउंडिंग आयत के अंदर स्थित हैं, एक क्वेरी जो बाउंडिंग आयत को प्रतिच्छेद नहीं करती है, वह किसी भी निहित वस्तु को प्रतिच्छेद नहीं कर सकती है। पत्ती स्तर पर, प्रत्येक आयत एक एकल वस्तु का वर्णन करता है; उच्च स्तर पर एकत्रीकरण में वस्तुओं की बढ़ती संख्या सम्मिलित होती है। इसे डेटा समूह के तेजी से सामान्य अनुमान के रूप में भी देखा जा सकता है।


[[ बी-वृक्ष | बी-]]ट्री के समान, आर-ट्री भी एक संतुलित खोज ट्री है (इसलिए सभी लीफ नोड्स समान गहराई पर हैं), डेटा को पृष्ठों में व्यवस्थित करता है, और डिस्क पर संचयन के लिए डिज़ाइन किया गया है (जैसा कि [[डेटाबेस]] में उपयोग किया जाता है)। प्रत्येक पृष्ठ में अधिकतम संख्या में प्रविष्टियाँ हो सकती हैं, जिन्हें अधिकांशतः <math>M</math> इस रूप में दर्शाया जाता है यह न्यूनतम भरण की भी आश्वासन देता है (रूट नोड को छोड़कर), चूँकि   प्रविष्टियों की अधिकतम संख्या के 30%-40% के न्यूनतम भरण के साथ सर्वश्रेष्ठ प्रदर्शन का अनुभव किया गया है ([[बी*-वृक्ष|बी*-]]ट्री 50% पृष्ठ भरने की आश्वासन देते हैं, और बी*- ट्री भी 66%)। इसका कारण बी-ट्रीों में संग्रहीत रैखिक डेटा के विपरीत स्थानिक डेटा के लिए आवश्यक अधिक जटिल संतुलन है।
[[ बी-वृक्ष | बी-]]ट्री के समान, आर-ट्री भी एक संतुलित खोज ट्री है (इसलिए सभी लीफ नोड्स समान गहराई पर हैं), डेटा को पृष्ठों में व्यवस्थित करता है, और डिस्क पर संचयन के लिए डिज़ाइन किया गया है (जैसा कि [[डेटाबेस]] में उपयोग किया जाता है)। प्रत्येक पृष्ठ में अधिकतम संख्या में प्रविष्टियाँ हो सकती हैं, जिन्हें अधिकांशतः <math>M</math> इस रूप में दर्शाया जाता है यह न्यूनतम भरण की भी आश्वासन देता है (रूट नोड को छोड़कर), चूँकि प्रविष्टियों की अधिकतम संख्या के 30%-40% के न्यूनतम भरण के साथ सर्वश्रेष्ठ प्रदर्शन का अनुभव किया गया है ([[बी*-वृक्ष|बी*-]]ट्री 50% पृष्ठ भरने की आश्वासन देते हैं, और बी*- ट्री भी 66%)। इसका कारण बी-ट्रीों में संग्रहीत रैखिक डेटा के विपरीत स्थानिक डेटा के लिए आवश्यक अधिक जटिल संतुलन है।


अधिकांश ट्रीों की तरह, खोज एल्गोरिदम (उदाहरण के लिए, [[प्रतिच्छेदन (सेट सिद्धांत)]], रोकथाम, निकटतम समीप खोज) अपेक्षाकृत सरल हैं। मुख्य विचार यह तय करने के लिए बाउंडिंग बॉक्स का उपयोग करना है कि उपट्री के अंदर खोजना है या नहीं है इस प्रकार, खोज के समय ट्री के अधिकांश नोड्स कभी नहीं पढ़े जाते हैं। बी-ट्री की तरह, आर-ट्री बड़े डेटा सेट और डेटाबेस के लिए उपयुक्त हैं, जहां जरूरत पड़ने पर नोड्स को मेमोरी में पेज किया जा सकता है, और पूरे ट्री को मुख्य मेमोरी में नहीं रखा जा सकता है। तथापि डेटा को मेमोरी (या कैश्ड) में फिट किया जा सकता है, अधिकांश वास्तविक अनुप्रयोगों में आर-ट्री समान्यत: सभी ऑब्जेक्ट्स की अनुभवहीन जांच पर प्रदर्शन लाभ प्रदान करेंगे जब ऑब्जेक्ट्स की संख्या कुछ सौ या उससे अधिक हो। चूँकि इन-मेमोरी अनुप्रयोगों के लिए, समान विकल्प हैं जो थोड़ा उत्तम प्रदर्शन प्रदान कर सकते हैं या वास्तव में प्रयुक्त करने में आसान हो सकते हैं। कंप्यूटर क्लस्टर में आर-ट्री के लिए इन-मेमोरी कंप्यूटिंग को बनाए रखने के लिए जहां कंप्यूटिंग नोड्स एक नेटवर्क द्वारा जुड़े हुए हैं, शोधकर्ताओं ने वितरित वातावरण में आर-ट्री के तहत डेटा-गहन अनुप्रयोगों को प्रयुक्त करने के लिए आरडीएमए ([[रिमोट डायरेक्ट मेमोरी एक्सेस]]) का उपयोग किया है।<ref>{{Cite conference |author= Mengbai Xiao, Hao Wang, Liang Geng, Rubao Lee, and Xiaodong Zhang| year=2022|pages=1–26|title="क्लस्टरों पर आर-ट्री के लिए एक आरडीएमए-सक्षम इन-मेमोरी कंप्यूटिंग प्लेटफ़ॉर्म"|conference= ACM Transactions on Spatial Algorithms and Systems|doi=10.1145/3503513 }}</ref> यह दृष्टिकोण तेजी से बड़े अनुप्रयोगों के लिए स्केलेबल है और आर-ट्री के लिए उच्च थ्रूपुट और कम विलंबता प्रदर्शन प्राप्त करता है।
अधिकांश ट्रीों की तरह, खोज एल्गोरिदम (उदाहरण के लिए, [[प्रतिच्छेदन (सेट सिद्धांत)|प्रतिच्छेदन (समूह सिद्धांत)]], रोकथाम, निकटतम समीप खोज) अपेक्षाकृत सरल हैं। मुख्य विचार यह तय करने के लिए बाउंडिंग बॉक्स का उपयोग करना है कि उपट्री के अंदर खोजना है या नहीं है इस प्रकार, खोज के समय ट्री के अधिकांश नोड्स कभी नहीं पढ़े जाते हैं। बी-ट्री की तरह, आर-ट्री बड़े डेटा समूह और डेटाबेस के लिए उपयुक्त हैं, जहां जरूरत पड़ने पर नोड्स को मेमोरी में पेज किया जा सकता है, और पूरे ट्री को मुख्य मेमोरी में नहीं रखा जा सकता है। तथापि डेटा को मेमोरी (या कैश्ड) में फिट किया जा सकता है, अधिकांश वास्तविक अनुप्रयोगों में आर-ट्री समान्यत: सभी ऑब्जेक्ट्स की अनुभवहीन जांच पर प्रदर्शन लाभ प्रदान करेंगे जब ऑब्जेक्ट्स की संख्या कुछ सौ या उससे अधिक हो। चूँकि इन-मेमोरी अनुप्रयोगों के लिए, समान विकल्प हैं जो थोड़ा उत्तम प्रदर्शन प्रदान कर सकते हैं या वास्तव में प्रयुक्त करने में आसान हो सकते हैं। कंप्यूटर क्लस्टर में आर-ट्री के लिए इन-मेमोरी कंप्यूटिंग को बनाए रखने के लिए जहां कंप्यूटिंग नोड्स एक नेटवर्क द्वारा जुड़े हुए हैं, शोधकर्ताओं ने वितरित वातावरण में आर-ट्री के तहत डेटा-गहन अनुप्रयोगों को प्रयुक्त करने के लिए आरडीएमए ([[रिमोट डायरेक्ट मेमोरी एक्सेस]]) का उपयोग किया है।<ref>{{Cite conference |author= Mengbai Xiao, Hao Wang, Liang Geng, Rubao Lee, and Xiaodong Zhang| year=2022|pages=1–26|title="क्लस्टरों पर आर-ट्री के लिए एक आरडीएमए-सक्षम इन-मेमोरी कंप्यूटिंग प्लेटफ़ॉर्म"|conference= ACM Transactions on Spatial Algorithms and Systems|doi=10.1145/3503513 }}</ref> यह दृष्टिकोण तेजी से बड़े अनुप्रयोगों के लिए स्केलेबल है और आर-ट्री के लिए उच्च थ्रूपुट और कम विलंबता प्रदर्शन प्राप्त करता है।


आर-ट्री की मुख्य कठिनाई एक कुशल ट्री का निर्माण करना है जो एक ओर संतुलित हो (जिससे पत्ती के नोड समान ऊंचाई पर हों) दूसरी ओर आयतें बहुत अधिक खाली जगह को कवर न करें और बहुत अधिक ओवरलैप न करें ( जिससे खोज के समय, कम उपवृक्षों को संसाधित करने की आवश्यकता हो)। उदाहरण के लिए, एक कुशल ट्री प्राप्त करने के लिए तत्वों को सम्मिलित करने का मूल विचार सदैव उस उपट्री में सम्मिलित करना है जिसके बाउंडिंग बॉक्स के कम से कम विस्तार की आवश्यकता होती है। एक बार जब वह पृष्ठ भर जाता है, तो डेटा को दो सेटों में विभाजित किया जाता है, जिनमें से प्रत्येक को न्यूनतम क्षेत्र को कवर करना चाहिए। आर-ट्री के लिए अधिकांश शोध और सुधारों का उद्देश्य ट्री के निर्माण के विधि में सुधार करना है और इसे दो उद्देश्यों में समूहीकृत किया जा सकता है: स्क्रैच से एक कुशल ट्री का निर्माण (जिसे बल्क-लोडिंग के रूप में जाना जाता है) और उपस्थित ट्री पर परिवर्तन करना (सम्मिलन और विलोपन) है।
आर-ट्री की मुख्य कठिनाई एक कुशल ट्री का निर्माण करना है जो एक ओर संतुलित हो (जिससे पत्ती के नोड समान ऊंचाई पर हों) दूसरी ओर आयतें बहुत अधिक खाली जगह को कवर न करें और बहुत अधिक ओवरलैप न करें ( जिससे खोज के समय, कम उपवृक्षों को संसाधित करने की आवश्यकता हो)। उदाहरण के लिए, एक कुशल ट्री प्राप्त करने के लिए अवयव ों को सम्मिलित करने का मूल विचार सदैव उस उपट्री में सम्मिलित करना है जिसके बाउंडिंग बॉक्स के कम से कम विस्तार की आवश्यकता होती है। एक बार जब वह पृष्ठ भर जाता है, तो डेटा को दो सेटों में विभाजित किया जाता है, जिनमें से प्रत्येक को न्यूनतम क्षेत्र को कवर करना चाहिए। आर-ट्री के लिए अधिकांश शोध और सुधारों का उद्देश्य ट्री के निर्माण के विधि में सुधार करना है और इसे दो उद्देश्यों में समूहीकृत किया जा सकता है: स्क्रैच से एक कुशल ट्री का निर्माण (जिसे बल्क-लोडिंग के रूप में जाना जाता है) और उपस्थित ट्री पर परिवर्तन करना (सम्मिलन और विलोपन) है।


आर-ट्रीज़ सबसे व्यर्थ स्थिति में अच्छे प्रदर्शन की आश्वासन नहीं देते हैं, किंतु समान्यता: वास्तविक दुनिया के डेटा के साथ अच्छा प्रदर्शन करते हैं।<ref>{{Cite book | last1 = Hwang | first1 = S. | last2 = Kwon | first2 = K. | last3 = Cha | first3 = S. K. | last4 = Lee | first4 = B. S. | chapter = Performance Evaluation of Main-Memory R-tree Variants | doi = 10.1007/978-3-540-45072-6_2 | title = स्थानिक और लौकिक डेटाबेस में प्रगति| series = Lecture Notes in Computer Science | volume = 2750 | pages = [https://archive.org/details/advancesinspatia0000sstd/page/10 10] | year = 2003 | isbn = 978-3-540-40535-1 | chapter-url-access = registration | chapter-url = https://archive.org/details/advancesinspatia0000sstd/page/10 }}</ref> जबकि सैद्धांतिक रुचि अधिक है, आर-ट्री का (थोक-भरा हुआ) प्राथमिकता आर-ट्री संस्करण सबसे व्यर्थ स्थिति में इष्टतम है,<ref name="prtree">{{Cite book | last1 = Arge | first1 = L. | author1-link = Lars Arge| last2 = De Berg | first2 = M. | last3 = Haverkort | first3 = H. J. | last4 = Yi | first4 = K. | chapter = The Priority R-tree | doi = 10.1145/1007568.1007608 | title = Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04 | pages = 347 | year = 2004 | isbn = 978-1581138597 | s2cid = 6817500 | chapter-url = http://www.win.tue.nl/~mdberg/Papers/prtree.pdf}}</ref> किंतु बढ़ती जटिलता के कारण अब तक व्यावहारिक अनुप्रयोगों में इस पर अधिक ध्यान नहीं दिया गया है।
आर-ट्रीज़ सबसे व्यर्थ स्थिति में अच्छे प्रदर्शन की आश्वासन नहीं देते हैं, किंतु समान्यता: वास्तविक दुनिया के डेटा के साथ अच्छा प्रदर्शन करते हैं।<ref>{{Cite book | last1 = Hwang | first1 = S. | last2 = Kwon | first2 = K. | last3 = Cha | first3 = S. K. | last4 = Lee | first4 = B. S. | chapter = Performance Evaluation of Main-Memory R-tree Variants | doi = 10.1007/978-3-540-45072-6_2 | title = स्थानिक और लौकिक डेटाबेस में प्रगति| series = Lecture Notes in Computer Science | volume = 2750 | pages = [https://archive.org/details/advancesinspatia0000sstd/page/10 10] | year = 2003 | isbn = 978-3-540-40535-1 | chapter-url-access = registration | chapter-url = https://archive.org/details/advancesinspatia0000sstd/page/10 }}</ref> जबकि सैद्धांतिक रुचि अधिक है, आर-ट्री का (थोक-भरा हुआ) प्राथमिकता आर-ट्री संस्करण सबसे व्यर्थ स्थिति में अधिकतम  है,<ref name="prtree">{{Cite book | last1 = Arge | first1 = L. | author1-link = Lars Arge| last2 = De Berg | first2 = M. | last3 = Haverkort | first3 = H. J. | last4 = Yi | first4 = K. | chapter = The Priority R-tree | doi = 10.1145/1007568.1007608 | title = Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04 | pages = 347 | year = 2004 | isbn = 978-1581138597 | s2cid = 6817500 | chapter-url = http://www.win.tue.nl/~mdberg/Papers/prtree.pdf}}</ref> किंतु बढ़ती सम्मिश्र्ता के कारण अब तक व्यावहारिक अनुप्रयोगों में इस पर अधिक ध्यान नहीं दिया गया है।


जब डेटा को आर-ट्री में व्यवस्थित किया जाता है, तो एक निश्चित दूरी के आर के निकटतम और के के निकटतम समीप ((किसी भी L<sup>p</sup>-नॉर्म के लिए)) सभी बिंदुओं की कुशलता से एक स्थानिक जुड़ाव का उपयोग करके गणना की जा सकती है।<ref>{{Cite journal | doi = 10.1145/170036.170075 | title = आर-पेड़ों का उपयोग करके स्थानिक जोड़ों का कुशल प्रसंस्करण| year = 1993 | last1 = Brinkhoff | first1 = T. | last2 = Kriegel | first2 = H. P. | author-link2=Hans-Peter Kriegel| last3 = Seeger | first3 = B. | journal = ACM SIGMOD Record | volume = 22 | issue = 2 | pages = 237| citeseerx = 10.1.1.72.4514 }}</ref><ref>{{Cite book|last1=Böhm|first1=Christian|last2=Krebs|first2=Florian|date=2003-09-01|title=के-निकटतम पड़ोसी द्वारा केडीडी अनुप्रयोगों का समर्थन करना|journal=Database and Expert Systems Applications|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=504–516|doi=10.1007/978-3-540-45227-0_50|isbn=9783540408062|citeseerx=10.1.1.71.454}}</ref> यह ऐसे प्रश्नों पर आधारित कई एल्गोरिदम के लिए लाभदायक है, उदाहरण के लिए स्थानीय आउटलायर फैक्टर डेली-क्लू,<ref>{{cite conference
जब डेटा को आर-ट्री में व्यवस्थित किया जाता है, तो एक निश्चित दूरी के आर के निकटतम और के के निकटतम समीप ((किसी भी L<sup>p</sup>-नॉर्म के लिए)) सभी बिंदुओं की कुशलता से एक स्थानिक जुड़ाव का उपयोग करके गणना की जा सकती है।<ref>{{Cite journal | doi = 10.1145/170036.170075 | title = आर-पेड़ों का उपयोग करके स्थानिक जोड़ों का कुशल प्रसंस्करण| year = 1993 | last1 = Brinkhoff | first1 = T. | last2 = Kriegel | first2 = H. P. | author-link2=Hans-Peter Kriegel| last3 = Seeger | first3 = B. | journal = ACM SIGMOD Record | volume = 22 | issue = 2 | pages = 237| citeseerx = 10.1.1.72.4514 }}</ref><ref>{{Cite book|last1=Böhm|first1=Christian|last2=Krebs|first2=Florian|date=2003-09-01|title=के-निकटतम पड़ोसी द्वारा केडीडी अनुप्रयोगों का समर्थन करना|journal=Database and Expert Systems Applications|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=504–516|doi=10.1007/978-3-540-45227-0_50|isbn=9783540408062|citeseerx=10.1.1.71.454}}</ref> यह ऐसे प्रश्नों पर आधारित अनेक  एल्गोरिदम के लिए लाभदायक है, उदाहरण के लिए स्थानीय आउटलायर फैक्टर डेली-क्लू,<ref>{{cite conference
  | last1 = Achtert | first1 = Elke
  | last1 = Achtert | first1 = Elke
  | last2 = Böhm | first2 = Christian
  | last2 = Böhm | first2 = Christian
Line 56: Line 56:
*[[एक्स-ट्री]]
*[[एक्स-ट्री]]


== एल्गोरिथम ==
== एल्गोरिथम                       ==


=== डेटा लेआउट ===
=== डेटा लेआउट ===
आर-ट्री में डेटा को उन पृष्ठों में व्यवस्थित किया जाता है जिनमें प्रविष्टियों की एक परिवर्तनीय संख्या हो सकती है (कुछ पूर्व-निर्धारित अधिकतम तक, और समान्यत:न्यूनतम भरण से ऊपर) नॉन-[[ लसीका नोड | लसीका नोड]] के अंदर प्रत्येक प्रविष्टि डेटा के दो टुकड़े संग्रहीत करती है: [[चाइल्ड नोड]] की पहचान करने का एक विधि , और इस चाइल्ड नोड के अंदर सभी प्रविष्टियों का [[ आकार निर्धारक बॉक्स |आकार निर्धारक बॉक्स]] लीफ नोड्स प्रत्येक बच्चे के लिए आवश्यक डेटा संग्रहीत करते हैं अधिकांशतः एक बिंदु या बाउंडिंग बॉक्स बच्चे का प्रतिनिधित्व करता है और बच्चे के लिए एक बाहरी पहचानकर्ता होता है। बिंदु डेटा के लिए, पत्ती प्रविष्टियाँ केवल बिंदु ही हो सकती हैं। बहुभुज डेटा के लिए (जिसमें अधिकांशतः बड़े बहुभुजों के संचयन की आवश्यकता होती है) सामान्य सेटअप ट्री में एक अद्वितीय पहचानकर्ता के साथ बहुभुज के केवल एमबीआर (न्यूनतम बाउंडिंग आयत) को संग्रहीत करना है।
आर-ट्री में डेटा को उन पृष्ठों में व्यवस्थित किया जाता है जिनमें प्रविष्टियों की एक परिवर्तनीय संख्या हो सकती है (कुछ पूर्व-निर्धारित अधिकतम तक, और समान्यत: न्यूनतम भरण से ऊपर) नॉन-[[ लसीका नोड | लसीका नोड]] के अंदर प्रत्येक प्रविष्टि डेटा के दो टुकड़े संग्रहीत करती है: [[चाइल्ड नोड]] की पहचान करने का एक विधि है , और इस चाइल्ड नोड के अंदर सभी प्रविष्टियों का [[ आकार निर्धारक बॉक्स |आकार निर्धारक बॉक्स]] लीफ नोड्स प्रत्येक बच्चे के लिए आवश्यक डेटा संग्रहीत करते हैं अधिकांशतः एक बिंदु या बाउंडिंग बॉक्स बच्चे का प्रतिनिधित्व करता है और बच्चे के लिए एक बाहरी पहचानकर्ता होता है। बिंदु डेटा के लिए, पत्ती प्रविष्टियाँ केवल बिंदु ही हो सकती हैं। बहुभुज डेटा के लिए (जिसमें अधिकांशतः बड़े बहुभुजों के संचयन की आवश्यकता होती है) सामान्य सेटअप ट्री में एक अद्वितीय पहचानकर्ता के साथ बहुभुज के केवल एमबीआर (न्यूनतम बाउंडिंग आयत) को संग्रहीत करना है।


=== खोजें ===
=== खोजें ===
श्रेणी खोज में, इनपुट एक खोज आयत (क्वेरी बॉक्स) है। खोजना अधिक सीमा तक [[बी+ पेड़|बी+ ट्री]] में खोजने के समान है। खोज ट्री के मूल नोड से प्रारंभ होती है। प्रत्येक आंतरिक नोड में संबंधित चाइल्ड नोड के लिए आयतों और संकेतकों का एक सेट होता है और प्रत्येक लीफ नोड में स्थानिक वस्तुओं के आयत होते हैं (कुछ स्थानिक वस्तु के लिए संकेतक वहां हो सकते हैं)। नोड में प्रत्येक आयत के लिए, यह तय करना होगा कि यह खोज आयत को ओवरलैप करता है या नहीं। यदि हां, तो संबंधित चाइल्ड नोड को भी खोजना होगा। खोज इस प्रकार पुनरावर्ती विधि से की जाती है जब तक कि सभी ओवरलैपिंग नोड्स का पता नहीं लगा लिया जाता। जब एक लीफ नोड तक पहुंच जाता है, तो निहित बाउंडिंग बॉक्स (आयत) का परीक्षण खोज आयत के विरुद्ध किया जाता है और उनके ऑब्जेक्ट (यदि कोई हों) को परिणाम सेट में डाल दिया जाता है यदि वे खोज आयत के अंदर होते हैं।
श्रेणी खोज में, इनपुट एक खोज आयत (क्वेरी बॉक्स) है। खोजना अधिक सीमा तक [[बी+ पेड़|बी+ ट्री]] में खोजने के समान है। खोज ट्री के मूल नोड से प्रारंभ होती है। प्रत्येक आंतरिक नोड में संबंधित चाइल्ड नोड के लिए आयतों और संकेतकों का एक समूह होता है और प्रत्येक लीफ नोड में स्थानिक वस्तुओं के आयत होते हैं (कुछ स्थानिक वस्तु के लिए संकेतक वहां हो सकते हैं)। नोड में प्रत्येक आयत के लिए, यह तय करना होगा कि यह खोज आयत को ओवरलैप करता है या नहीं। यदि हां, तो संबंधित चाइल्ड नोड को भी खोजना होगा। खोज इस प्रकार पुनरावर्ती विधि से की जाती है जब तक कि सभी ओवरलैपिंग नोड्स का पता नहीं लगा लिया जाता। जब एक लीफ नोड तक पहुंच जाता है, तो निहित बाउंडिंग बॉक्स (आयत) का परीक्षण खोज आयत के विरुद्ध किया जाता है और उनके ऑब्जेक्ट (यदि कोई हों) को परिणाम समूह में डाल दिया जाता है यदि वे खोज आयत के अंदर होते हैं।


निकटतम समीप खोज जैसी प्राथमिकता वाली खोज के लिए, क्वेरी में एक बिंदु या आयत होता है। रूट नोड को प्राथमिकता कतार में डाला गया है। जब तक कतार खाली नहीं हो जाती या वांछित संख्या में परिणाम नहीं आ जाते, कतार में निकटतम प्रविष्टि को संसाधित करके खोज जारी रहती है। ट्री नोड्स का विस्तार किया जाता है और उनके बच्चों को पुनः सम्मिलित किया जाता है। कतार में सामने आने पर लीफ प्रविष्टियाँ लौटा दी जाती हैं।<ref>{{Cite conference | doi = 10.1109/ICICS.1997.652114| chapter = Fast k nearest neighbour search for R-tree family| title = Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237)| pages = 924| year = 1997| last1 = Kuan | first1 = J.| last2 = Lewis | first2 = P.| isbn = 0-7803-3676-3}}</ref> इस दृष्टिकोण का उपयोग विभिन्न दूरी आव्यूह ` के साथ किया जा सकता है, जिसमें भौगोलिक डेटा के लिए ग्रेट-सर्कल दूरी भी सम्मिलित   है।<ref name=geodetic/>
निकटतम समीप खोज जैसी प्राथमिकता वाली खोज के लिए, क्वेरी में एक बिंदु या आयत होता है। रूट नोड को प्राथमिकता श्रंखला  में डाला गया है। जब तक श्रंखला  खाली नहीं हो जाती या वांछित संख्या में परिणाम नहीं आ जाते, श्रंखला  में निकटतम प्रविष्टि को संसाधित करके खोज जारी रहती है। ट्री नोड्स का विस्तार किया जाता है और उनके बच्चों को पुनः सम्मिलित किया जाता है। श्रंखला  में सामने आने पर लीफ प्रविष्टियाँ लौटा दी जाती हैं।<ref>{{Cite conference | doi = 10.1109/ICICS.1997.652114| chapter = Fast k nearest neighbour search for R-tree family| title = Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237)| pages = 924| year = 1997| last1 = Kuan | first1 = J.| last2 = Lewis | first2 = P.| isbn = 0-7803-3676-3}}</ref> इस दृष्टिकोण का उपयोग विभिन्न दूरी आव्यूह `के साथ किया जा सकता है, जिसमें भौगोलिक डेटा के लिए ग्रेट-सर्कल दूरी भी सम्मिलित है।<ref name=geodetic/>




Line 71: Line 72:


==== सम्मिलन उपट्री चुनना ====
==== सम्मिलन उपट्री चुनना ====
एल्गोरिदम को यह तय करने की आवश्यकता है कि किस सबट्री को सम्मिलित करना है। जब कोई डेटा ऑब्जेक्ट पूरी तरह से एक ही आयत में समाहित होता है, तो विकल्प स्पष्ट होता है। जब कई विकल्प या आयतों को बढ़ाने की आवश्यकता होती है, तो विकल्प ट्री के प्रदर्शन पर महत्वपूर्ण प्रभाव डाल सकता है।
एल्गोरिदम को यह तय करने की आवश्यकता है कि किस उपट्री को सम्मिलित करना है। जब कोई डेटा ऑब्जेक्ट पूरी तरह से एक ही आयत में समाहित होता है, तो विकल्प स्पष्ट होता है। जब अनेक  विकल्प या आयतों को बढ़ाने की आवश्यकता होती है, तो विकल्प ट्री के प्रदर्शन पर महत्वपूर्ण प्रभाव डाल सकता है।


ऑब्जेक्ट को उस सबट्री में डाला जाता है जिसे सबसे कम विस्तार की आवश्यकता होती है। एक मिश्रण अनुमानी का प्रयोग सर्वत्र किया जाता है। आगे क्या होता है यह ओवरलैप को कम करने की प्रयाश करता है (संबंधों के स्थिति में, कम से कम विस्तार और फिर सबसे कम क्षेत्र को प्राथमिकता दें); उच्च स्तर पर, यह आर-ट्री के समान व्यवहार करता है, किंतु संबंधों पर फिर से छोटे क्षेत्र वाले उपट्री को प्राथमिकता देता है। आर*-ट्री में आयतों का घटा हुआ ओवरलैप पारंपरिक आर-ट्री की तुलना में प्रमुख लाभों में से एक है।
ऑब्जेक्ट को उस उपट्री में डाला जाता है जिसे सबसे कम विस्तार की आवश्यकता होती है। एक मिश्रण अनुमानी का प्रयोग सर्वत्र किया जाता है। आगे क्या होता है यह ओवरलैप को कम करने की प्रयाश करता है (संबंधों के स्थिति में, कम से कम विस्तार और फिर सबसे कम क्षेत्र को प्राथमिकता दें); उच्च स्तर पर, यह आर-ट्री के समान व्यवहार करता है, किंतु संबंधों पर फिर से छोटे क्षेत्र वाले उपट्री को प्राथमिकता देता है। आर*-ट्री में आयतों का घटा हुआ ओवरलैप पारंपरिक आर-ट्री की तुलना में प्रमुख लाभों में से एक है।


==== एक अतिप्रवाहित नोड को विभाजित करना ====
==== एक अतिप्रवाहित नोड को विभाजित करना ====
चूँकि एक नोड की सभी वस्तुओं को दो नोड्स में पुनर्वितरित करने के लिए विकल्पों की एक घातीय संख्या होती है, सर्वोत्तम विभाजन खोजने के लिए एक अनुमान को नियोजित करने की आवश्यकता होती है। उत्कृष्ट आर-ट्री में, गुटमैन ने दो ऐसे अनुमान प्रस्तावित किए, जिन्हें क्वाड्रैटिकस्प्लिट और लीनियरस्प्लिट कहा जाता है। द्विघात विभाजन में, एल्गोरिदम आयतों की जोड़ी की खोज करता है जो एक ही नोड में सबसे व्यर्थ संयोजन है, और उन्हें दो नए समूहों में प्रारंभिक वस्तुओं के रूप में रखता है। इसके बाद यह उस प्रविष्टि की खोज करता है जिसमें किसी एक समूह (क्षेत्र वृद्धि के संदर्भ में) के लिए सबसे शसक्त प्राथमिकता है और इस समूह को तब तक ऑब्जेक्ट आवंटित करता है जब तक कि सभी ऑब्जेक्ट असाइन नहीं किए जाते (न्यूनतम भरण को संतुष्ट करते हुए)।
चूँकि एक नोड की सभी वस्तुओं को दो नोड्स में पुनर्वितरित करने के लिए विकल्पों की एक घातीय संख्या होती है, सर्वोत्तम विभाजन खोजने के लिए एक अनुमान को नियोजित करने की आवश्यकता होती है। उत्कृष्ट आर-ट्री में, गुटमैन ने दो ऐसे अनुमान प्रस्तावित किए, जिन्हें क्वाड्रैटिकस्प्लिट और लीनियरस्प्लिट कहा जाता है। द्विघात विभाजन में, एल्गोरिदम आयतों की जोड़ी की खोज करता है जो एक ही नोड में सबसे व्यर्थ संयोजन है, और उन्हें दो नए समूहों में प्रारंभिक वस्तुओं के रूप में रखता है। इसके बाद यह उस प्रविष्टि की खोज करता है जिसमें किसी एक समूह (क्षेत्र वृद्धि के संदर्भ में) के लिए सबसे शसक्त प्राथमिकता है और इस समूह को तब तक ऑब्जेक्ट आवंटित करता है जब तक कि सभी ऑब्जेक्ट असाइन नहीं किए जाते (न्यूनतम भरण को संतुष्ट करते हुए)।


अन्य विभाजन रणनीतियाँ भी हैं जैसे ग्रीन्स स्प्लिट,<ref name="greene">{{Cite book | last1 = Greene | first1 = D. | chapter = An implementation and performance analysis of spatial data access methods | doi = 10.1109/ICDE.1989.47268 | title = [1989] Proceedings. Fifth International Conference on Data Engineering | pages = 606–615 | year = 1989 | isbn = 978-0-8186-1915-1 | s2cid = 7957624 }}</ref> आर*-ट्री विभाजन अनुमानी<ref name="rstar">{{Cite book | last1 = Beckmann | first1 = N. | last2 = Kriegel | first2 = H. P. | author-link2 = Hans-Peter Kriegel| last3 = Schneider | first3 = R. | last4 = Seeger | first4 = B. | chapter = The R*-tree: an efficient and robust access method for points and rectangles | doi = 10.1145/93597.98741 | title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data – SIGMOD '90 | pages = 322 | year = 1990 | isbn = 978-0897913652 | chapter-url = http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf| citeseerx = 10.1.1.129.3731 | s2cid = 11567855 }}</ref> (जो फिर से ओवरलैप को कम करने की प्रयाश करता है, किंतु द्विघात पृष्ठों को भी प्राथमिकता देता है) या एंग और टैन द्वारा प्रस्तावित रैखिक विभाजन एल्गोरिथ्म<ref name="ang-tan">{{cite conference | last1= Ang | first1 = C. H. | last2 = Tan | first2 = T. C. | editor1-first = Michel | editor1-last = Scholl | editor2-first = Agnès | editor2-last = Voisard | year = 1997 | title = आर-पेड़ों के लिए नया रैखिक नोड विभाजन एल्गोरिदम| book-title = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 | volume = 1262 |series=Lecture Notes in Computer Science | publisher=Springer | pages = 337–349 | doi = 10.1007/3-540-63238-7_38}}</ref> (जो चूँकि   बहुत अनियमित आयत उत्पन्न कर सकता है, जो कई वास्तविक विश्व रेंज और विंडो प्रश्नों के लिए कम प्रदर्शन करने वाला है)। अधिक उन्नत विभाजन अनुमानी होने के अतिरिक्त , आर *-ट्री कुछ नोड सदस्यों को फिर से सम्मिलित करके एक नोड को विभाजित करने से बचने की भी प्रयाश करता है, जो कि बी-ट्री ओवरफ्लोिंग नोड्स को संतुलित करने के विधि के समान है। यह ओवरलैप को कम करने और इस प्रकार ट्री के प्रदर्शन को बढ़ाने के लिए भी दिखाया गया था।
अन्य विभाजन रणनीतियाँ भी हैं जैसे ग्रीन्स स्प्लिट,<ref name="greene">{{Cite book | last1 = Greene | first1 = D. | chapter = An implementation and performance analysis of spatial data access methods | doi = 10.1109/ICDE.1989.47268 | title = [1989] Proceedings. Fifth International Conference on Data Engineering | pages = 606–615 | year = 1989 | isbn = 978-0-8186-1915-1 | s2cid = 7957624 }}</ref> आर*-ट्री विभाजन अनुमानी<ref name="rstar">{{Cite book | last1 = Beckmann | first1 = N. | last2 = Kriegel | first2 = H. P. | author-link2 = Hans-Peter Kriegel| last3 = Schneider | first3 = R. | last4 = Seeger | first4 = B. | chapter = The R*-tree: an efficient and robust access method for points and rectangles | doi = 10.1145/93597.98741 | title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data – SIGMOD '90 | pages = 322 | year = 1990 | isbn = 978-0897913652 | chapter-url = http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf| citeseerx = 10.1.1.129.3731 | s2cid = 11567855 }}</ref> (जो फिर से ओवरलैप को कम करने की प्रयाश करता है, किंतु द्विघात पृष्ठों को भी प्राथमिकता देता है) या एंग और टैन द्वारा प्रस्तावित रैखिक विभाजन एल्गोरिथ्म<ref name="ang-tan">{{cite conference | last1= Ang | first1 = C. H. | last2 = Tan | first2 = T. C. | editor1-first = Michel | editor1-last = Scholl | editor2-first = Agnès | editor2-last = Voisard | year = 1997 | title = आर-पेड़ों के लिए नया रैखिक नोड विभाजन एल्गोरिदम| book-title = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 | volume = 1262 |series=Lecture Notes in Computer Science | publisher=Springer | pages = 337–349 | doi = 10.1007/3-540-63238-7_38}}</ref> (जो चूँकि बहुत अनियमित आयत उत्पन्न कर सकता है, जो अनेक  वास्तविक विश्व रेंज और विंडो प्रश्नों के लिए कम प्रदर्शन करने वाला है)। अधिक उन्नत विभाजन अनुमानी होने के अतिरिक्त , आर *-ट्री कुछ नोड सदस्यों को फिर से सम्मिलित करके एक नोड को विभाजित करने से बचने की भी प्रयाश करता है, जो कि बी-ट्री ओवरफ्लोिंग नोड्स को संतुलित करने के विधि के समान है। यह ओवरलैप को कम करने और इस प्रकार ट्री के प्रदर्शन को बढ़ाने के लिए भी दिखाया गया था।


अंत में, एक्स-ट्री<ref name="xtree2">{{Cite journal| first1 = Stefan | last1 = Berchtold| first2 = Daniel A. | last2 = Keim| first3 = Hans-Peter | last3 = Kriegel| author3-link = Hans-Peter Kriegel| title = The X-Tree: An Index Structure for High-Dimensional Data| journal = Proceedings of the 22nd VLDB Conference| place = Mumbai, India| year = 1996| pages = 28–39| url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/x-tree.ps}}</ref> इसे एक आर*-ट्री वेरिएंट के रूप में देखा जा सकता है जो एक नोड को विभाजित नहीं करने का निर्णय ले सकता है, किंतु सभी अतिरिक्त प्रविष्टियों वाले एक तथाकथित सुपर-नोड का निर्माण कर सकता है, जब इसे एक अच्छा विभाजन नहीं मिलता है (विशेष रूप से उच्च के लिए) आयामी डेटा)।
अंत में, एक्स-ट्री<ref name="xtree2">{{Cite journal| first1 = Stefan | last1 = Berchtold| first2 = Daniel A. | last2 = Keim| first3 = Hans-Peter | last3 = Kriegel| author3-link = Hans-Peter Kriegel| title = The X-Tree: An Index Structure for High-Dimensional Data| journal = Proceedings of the 22nd VLDB Conference| place = Mumbai, India| year = 1996| pages = 28–39| url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/x-tree.ps}}</ref> इसे एक आर*-ट्री वेरिएंट के रूप में देखा जा सकता है जो एक नोड को विभाजित नहीं करने का निर्णय ले सकता है, किंतु सभी अतिरिक्त प्रविष्टियों वाले एक तथाकथित सुपर-नोड का निर्माण कर सकता है, जब इसे एक अच्छा विभाजन नहीं मिलता है (विशेष रूप से उच्च के लिए) आयामी डेटा)।
Line 85: Line 86:
|title=Effect of different splitting heuristics on a database with US postal districts
|title=Effect of different splitting heuristics on a database with US postal districts
|width=300 | height=300 | align=center | lines=6
|width=300 | height=300 | align=center | lines=6
|File:R-tree_with_Guttman's_quadratic_split.png|Guttman's quadratic split.<ref name="guttman" /><br />Pages in this tree overlap a lot.
|File:R-tree_with_Guttman's_quadratic_split.png|गुटमैन का द्विघात विभाजन.<ref name="guttman" /><br />इस पेड़ के पन्ने बहुत अधिक ओवरलैप होते हैं.
|File:R-tree built with Guttman's linear split.png|Guttman's linear split.<ref name="guttman" /><br />Even worse structure, but also faster to construct.
|File:R-tree built with Guttman's linear split.png|गुटमैन का रैखिक विभाजन.<ref name="guttman" /><br />संरचना और भी ख़राब, लेकिन निर्माण में भी तेज़।
|File:R-tree built with Greenes Split.png|Greene's split.<ref name="greene" /> Pages overlap much less than with Guttman's strategy.
|File:R-tree built with Greenes Split.png|ग्रीन का विभाजन.<ref name="greene" /> गुटमैन की रणनीति की तुलना में पेज बहुत कम ओवरलैप होते हैं।
|File:R-tree built with Ang-Tan linear split.png|Ang-Tan linear split.<ref name="ang-tan" /><br />This strategy produces sliced pages, which often yield bad query performance.
|File:R-tree built with Ang-Tan linear split.png|एंग-टैन रैखिक विभाजन.<ref name="ang-tan" /><br />यह रणनीति कटे हुए पृष्ठ तैयार करती है, जो अधिकांशतः व्यर्थ क्वेरी प्रदर्शन उत्पन्न करते हैं।
|File:R*-tree built using topological split.png |[[R* tree]] topological split.<ref name="rstar" /><br /> The pages overlap much less since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy prefers quadratic pages, which yields better performance for common map applications.
|File:R*-tree built using topological split.png |[[R* tree]] टोपोलॉजिकल विभाजन.<ref name="rstar" /><br /> चूंकि आर*-ट्री पेज ओवरलैप को कम करने की प्रयास करता है, इसलिए पेज बहुत कम ओवरलैप होते हैं, और पुन: सम्मिलन ट्री को और अधिक अनुकूलित करता है। विभाजित रणनीति द्विघात पृष्ठों को प्राथमिकता देती है, जो सामान्य मानचित्र अनुप्रयोगों के लिए उत्तम  प्रदर्शन प्रदान करती है।
|File:R*-tree bulk loaded with sort-tile-recursive.png|Bulk loaded [[R* tree]] using Sort-Tile-Recursive (STR).<br />The leaf pages do not overlap at all, and the directory pages overlap only little. This is a very efficient tree, but it requires the data to be completely known beforehand.
|File:R*-tree bulk loaded with sort-tile-recursive.png|सॉर्ट-टाइल-रिकर्सिव (एसटीआर) का उपयोग करके थोक में लोड किया गया [[आर* ट्री]]।<br />चूंकि आर*-ट्री पेज ओवरलैप को कम करने की प्रयास करता है, इसलिए पेज बहुत कम ओवरलैप होते हैं, और पुन: सम्मिलन ट्री को और अधिक अनुकूलित करता है। विभाजित रणनीति द्विघात पृष्ठों को प्राथमिकता देती है, जो सामान्य मानचित्र अनुप्रयोगों के लिए उत्तम प्रदर्शन प्रदान करती है।|File:M-tree built with MMRad split.png|[[एम-ट्री]] आर-ट्री के समान हैं, लेकिन नेस्टेड गोलाकार पृष्ठों का उपयोग करते हैं.<br />चूँकि, इन पृष्ठों को विभाजित करना अधिक सम्मिश्र  है और पृष्ठ सामान्यतः बहुत अधिक ओवरलैप होते हैं।
|File:M-tree built with MMRad split.png|[[M-tree]]s are similar to the R-tree, but use nested spherical pages.<br />Splitting these pages is, however, much more complicated and pages usually overlap much more.
}}
}}


=== विलोपन ===
=== विलोपन ===
किसी पृष्ठ से किसी प्रविष्टि को हटाने के लिए मूल पृष्ठों के बाउंडिंग आयतों को अद्यतन करने की आवश्यकता हो सकती है। चूँकि जब कोई पृष्ठ कम भरा होता है, तो वह अपने समिपों के साथ संतुलित नहीं होगा। इसके अतिरिक्त , पेज को विघटित कर दिया जाएगा और उसके सभी बच्चों (जो कि केवल लीफ ऑब्जेक्ट ही नहीं, किंतु सबट्री भी हो सकते हैं) को फिर से सम्मिलित कर दिया जाएगा। यदि इस प्रक्रिया के समय रूट नोड में एक भी तत्व है, तो ट्री की ऊंचाई कम हो सकती है।
किसी पृष्ठ से किसी प्रविष्टि को हटाने के लिए मूल पृष्ठों के बाउंडिंग आयतों को अद्यतन करने की आवश्यकता हो सकती है। चूँकि जब कोई पृष्ठ कम भरा होता है, तो वह अपने समिपों के साथ संतुलित नहीं होगा। इसके अतिरिक्त , पेज को विघटित कर दिया जाएगा और उसके सभी बच्चों (जो कि केवल लीफ ऑब्जेक्ट ही नहीं, किंतु सबट्री भी हो सकते हैं) को फिर से सम्मिलित कर दिया जाएगा। यदि इस प्रक्रिया के समय रूट नोड में एक भी अवय  है, तो ट्री की ऊंचाई कम हो सकती है।


=== थोक-लोडिंग ===
=== थोक-लोडिंग ===


* निकटतम-एक्स: वस्तुओं को उनके पहले निर्देशांक (एक्स) के अनुसार क्रमबद्ध किया जाता है और फिर वांछित आकार के पृष्ठों में विभाजित किया जाता है।
* निकटतम-एक्स: वस्तुओं को उनके पहले निर्देशांक (एक्स) के अनुसार क्रमबद्ध किया जाता है और फिर वांछित आकार के पृष्ठों में विभाजित किया जाता है।
* पैक्ड हिल्बर्ट आर-ट्री: निकटतम-एक्स की भिन्नता, किंतु एक्स समन्वय का उपयोग करने के अतिरिक्त आयत के केंद्र के हिल्बर्ट मान का उपयोग करके सॉर्ट करना है। इसकी कोई आश्वासन नहीं है कि पेज ओवरलैप नहीं होंगे।
* पैक्ड हिल्बर्ट आर-ट्री: निकटतम-एक्स की भिन्नता, किंतु एक्स समन्वय का उपयोग करने के अतिरिक्त आयत के केंद्र के हिल्बर्ट मान का उपयोग करके सॉर्ट करना है। इसकी कोई आश्वासन नहीं है कि पेज ओवरलैप नहीं होंगे।
*सॉर्ट-टाइल-रिकर्सिव (एसटीआर):<ref>{{cite document | first1 = Scott T. | last1 = Leutenegger | first2 = Jeffrey M. | last2 = Edgington | first3 = Mario A. | last3 = Lopez | url = https://archive.org/details/nasa_techdoc_19970016975 | title = STR: A Simple and Efficient Algorithm for R-Tree Packing |date=February 1997}}</ref> निकटतम-एक्स का एक और रूपांतर, जो आवश्यक पत्तियों की कुल संख्या का अनुमान लगाता है <math>l=\lceil \text{number of objects} / \text{capacity}\rceil</math>, इसे <math>s=\lceil l^{1/d}\rceil</math> के रूप में प्राप्त करने के लिए प्रत्येक आयाम में आवश्यक विभाजन कारक, फिर 1-आयामी सॉर्टिंग का उपयोग करके प्रत्येक आयाम को क्रमिक रूप से <math>s</math> समान आकार के विभाजन में विभाजित करता है। परिणामी पृष्ठ, यदि वे एक से अधिक पृष्ठों पर अधिकृत करते हैं, तो उसी एल्गोरिथ्म का उपयोग करके फिर से थोक में लोड किए जाते हैं। बिंदु डेटा के लिए, लीफ़ नोड्स ओवरलैप नहीं होंगे, और डेटा स्थान को लगभग समान आकार के पृष्ठों में "टाइल" करेंगे।
*सॉर्ट-टाइल-रिकर्सिव (एसटीआर):<ref>{{cite document | first1 = Scott T. | last1 = Leutenegger | first2 = Jeffrey M. | last2 = Edgington | first3 = Mario A. | last3 = Lopez | url = https://archive.org/details/nasa_techdoc_19970016975 | title = STR: A Simple and Efficient Algorithm for R-Tree Packing |date=February 1997}}</ref> निकटतम-एक्स का एक और रूपांतर, जो आवश्यक पत्तियों की कुल संख्या का अनुमान लगाता है <math>l=\lceil \text{number of objects} / \text{capacity}\rceil                                                                                                                                            
                                                                                                                                                                                                                   
                                                                                                                                                                                                                          </math>, इसे <math>s=\lceil l^{1/d}\rceil                                                                                                                                                                          
                                                                                                                                                                                                                     
                        </math> के रूप में प्राप्त करने के लिए प्रत्येक आयाम में आवश्यक विभाजन कारक, फिर 1-आयामी सॉर्टिंग का उपयोग करके प्रत्येक आयाम को क्रमिक रूप से <math>s</math> समान आकार के विभाजन में विभाजित करता है। परिणामी पृष्ठ, यदि वे एक से अधिक पृष्ठों पर अधिकृत करते हैं, तो उसी एल्गोरिथ्म का उपयोग करके फिर से थोक में लोड किए जाते हैं। बिंदु डेटा के लिए, लीफ़ नोड्स ओवरलैप नहीं होंगे, और डेटा स्थान को लगभग समान आकार के पृष्ठों में "टाइल" करेंगे।
* ओवरलैप मिनिमाइजिंग टॉप-डाउन (ओएमटी):<ref>{{cite document | first1 = Taewon | last1 = Lee | first2 = Sukho | last2 = Lee | url = http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf | title =  OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree | date=June 2003}}</ref> टॉप-डाउन दृष्टिकोण का उपयोग करके एसटीआर में सुधार जो स्लाइस के बीच ओवरलैप को कम करता है और क्वेरी प्रदर्शन में सुधार करता है।
* ओवरलैप मिनिमाइजिंग टॉप-डाउन (ओएमटी):<ref>{{cite document | first1 = Taewon | last1 = Lee | first2 = Sukho | last2 = Lee | url = http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf | title =  OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree | date=June 2003}}</ref> टॉप-डाउन दृष्टिकोण का उपयोग करके एसटीआर में सुधार जो स्लाइस के बीच ओवरलैप को कम करता है और क्वेरी प्रदर्शन में सुधार करता है।
* प्राथमिकता आर-वृक्ष
* प्राथमिकता आर-वृक्ष


== यह भी देखें ==
== यह भी देखें                                                                                 ==


* [[खंड वृक्ष]]
* [[खंड वृक्ष]]
Line 121: Line 125:
* {{commons category-inline|R-tree}}
* {{commons category-inline|R-tree}}


{{DEFAULTSORT:R-Tree}}[[Category: आर-वृक्ष| आर-वृक्ष]]
{{DEFAULTSORT:R-Tree}}


 
[[Category:All articles with bare URLs for citations]]
 
[[Category:Articles with PDF format bare URLs for citations]]
[[Category: Machine Translated Page]]
[[Category:Articles with bare URLs for citations from March 2022]]
[[Category:Created On 10/07/2023]]
[[Category:Articles with hatnote templates targeting a nonexistent page|R-Tree]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 errors]]
[[Category:CS1 maint]]
[[Category:Created On 10/07/2023|R-Tree]]
[[Category:Lua-based templates|R-Tree]]
[[Category:Machine Translated Page|R-Tree]]
[[Category:Pages with script errors|R-Tree]]
[[Category:Short description with empty Wikidata description|R-Tree]]
[[Category:Templates Vigyan Ready|R-Tree]]
[[Category:Templates that add a tracking category|R-Tree]]
[[Category:Templates that generate short descriptions|R-Tree]]
[[Category:Templates using TemplateData|R-Tree]]
[[Category:आर-वृक्ष| आर-वृक्ष]]

Latest revision as of 13:30, 3 August 2023

This article is about डेटा संरचना. For मीट्रिक स्थान का प्रकार, see वास्तविक ट्री.
R-tree
Typetree
Invented1984
Invented byAntonin Guttman
Time complexity in big O notation
Algorithm Average Worst case
Search O(logMn) O(n)[1]
Insert O(n)
2डी आयतों के लिए आर-ट्री का सरल उदाहरण
ELKI का उपयोग करके 3D बिंदुओं के लिए R*-ट्री का विज़ुअलाइज़ेशन (क्यूब्स निर्देशिका पृष्ठ हैं)

आर-ट्री ट्री डेटा संरचनाएं हैं जिनका उपयोग स्थानिक सूचकांक के लिए किया जाता है, अर्थात, भौगोलिक समन्वय प्रणाली, आयत या बहुभुज जैसी बहु-आयामी जानकारी को अनुक्रमित करने के लिए आर-ट्री का प्रस्ताव 1984 में एंटोनिन गुटमैन द्वारा किया गया था[2] और इसे सैद्धांतिक और व्यावहारिक दोनों संदर्भों में महत्वपूर्ण उपयोग मिला है।[3] आर-ट्री के लिए एक सामान्य वास्तविक दुनिया का उपयोग स्थानिक वस्तुओं जैसे कि रेस्तरां स्थानों या बहुभुजों को संग्रहीत करना हो सकता है, जिनसे विशिष्ट मानचित्र बने होते हैं: सड़कें, इमारतें, झीलों की रूपरेखा, समुद्र तट, आदि और फिर प्रश्नों के तुरंत उत्तर खोजे जाते है जैसे कि मेरे वर्तमान स्थान के 2 किमी के अंदर सभी संग्रहालय खोजे, मेरे स्थान के 2 किमी के अंदर सभी सड़क खंडों को पुनः प्राप्त करें (उन्हें नेविगेशन प्रणाली में प्रदर्शित करने के लिए) या निकटतम गैस स्टेशन खोजे जाते है (चूँकि सड़कों को ध्यान में नहीं रखते हुए) आर-ट्री ग्रेट-सर्कल दूरी सहित विभिन्न दूरी आव्यूह के लिए निकटतम समीप खोज[4] को भी तेज कर सकता है।[5]


आर-ट्री विचार

डेटा संरचना का मुख्य विचार आस-पास की वस्तुओं को समूहित करना और उन्हें ट्री के अगले उच्च स्तर में उनकी न्यूनतम सीमा वाली आयत के साथ प्रस्तुत करना है; आर-ट्री में आर आयत के लिए है। चूँकि सभी वस्तुएँ इस बाउंडिंग आयत के अंदर स्थित हैं, एक क्वेरी जो बाउंडिंग आयत को प्रतिच्छेद नहीं करती है, वह किसी भी निहित वस्तु को प्रतिच्छेद नहीं कर सकती है। पत्ती स्तर पर, प्रत्येक आयत एक एकल वस्तु का वर्णन करता है; उच्च स्तर पर एकत्रीकरण में वस्तुओं की बढ़ती संख्या सम्मिलित होती है। इसे डेटा समूह के तेजी से सामान्य अनुमान के रूप में भी देखा जा सकता है।

बी-ट्री के समान, आर-ट्री भी एक संतुलित खोज ट्री है (इसलिए सभी लीफ नोड्स समान गहराई पर हैं), डेटा को पृष्ठों में व्यवस्थित करता है, और डिस्क पर संचयन के लिए डिज़ाइन किया गया है (जैसा कि डेटाबेस में उपयोग किया जाता है)। प्रत्येक पृष्ठ में अधिकतम संख्या में प्रविष्टियाँ हो सकती हैं, जिन्हें अधिकांशतः इस रूप में दर्शाया जाता है यह न्यूनतम भरण की भी आश्वासन देता है (रूट नोड को छोड़कर), चूँकि प्रविष्टियों की अधिकतम संख्या के 30%-40% के न्यूनतम भरण के साथ सर्वश्रेष्ठ प्रदर्शन का अनुभव किया गया है (बी*-ट्री 50% पृष्ठ भरने की आश्वासन देते हैं, और बी*- ट्री भी 66%)। इसका कारण बी-ट्रीों में संग्रहीत रैखिक डेटा के विपरीत स्थानिक डेटा के लिए आवश्यक अधिक जटिल संतुलन है।

अधिकांश ट्रीों की तरह, खोज एल्गोरिदम (उदाहरण के लिए, प्रतिच्छेदन (समूह सिद्धांत), रोकथाम, निकटतम समीप खोज) अपेक्षाकृत सरल हैं। मुख्य विचार यह तय करने के लिए बाउंडिंग बॉक्स का उपयोग करना है कि उपट्री के अंदर खोजना है या नहीं है इस प्रकार, खोज के समय ट्री के अधिकांश नोड्स कभी नहीं पढ़े जाते हैं। बी-ट्री की तरह, आर-ट्री बड़े डेटा समूह और डेटाबेस के लिए उपयुक्त हैं, जहां जरूरत पड़ने पर नोड्स को मेमोरी में पेज किया जा सकता है, और पूरे ट्री को मुख्य मेमोरी में नहीं रखा जा सकता है। तथापि डेटा को मेमोरी (या कैश्ड) में फिट किया जा सकता है, अधिकांश वास्तविक अनुप्रयोगों में आर-ट्री समान्यत: सभी ऑब्जेक्ट्स की अनुभवहीन जांच पर प्रदर्शन लाभ प्रदान करेंगे जब ऑब्जेक्ट्स की संख्या कुछ सौ या उससे अधिक हो। चूँकि इन-मेमोरी अनुप्रयोगों के लिए, समान विकल्प हैं जो थोड़ा उत्तम प्रदर्शन प्रदान कर सकते हैं या वास्तव में प्रयुक्त करने में आसान हो सकते हैं। कंप्यूटर क्लस्टर में आर-ट्री के लिए इन-मेमोरी कंप्यूटिंग को बनाए रखने के लिए जहां कंप्यूटिंग नोड्स एक नेटवर्क द्वारा जुड़े हुए हैं, शोधकर्ताओं ने वितरित वातावरण में आर-ट्री के तहत डेटा-गहन अनुप्रयोगों को प्रयुक्त करने के लिए आरडीएमए (रिमोट डायरेक्ट मेमोरी एक्सेस) का उपयोग किया है।[6] यह दृष्टिकोण तेजी से बड़े अनुप्रयोगों के लिए स्केलेबल है और आर-ट्री के लिए उच्च थ्रूपुट और कम विलंबता प्रदर्शन प्राप्त करता है।

आर-ट्री की मुख्य कठिनाई एक कुशल ट्री का निर्माण करना है जो एक ओर संतुलित हो (जिससे पत्ती के नोड समान ऊंचाई पर हों) दूसरी ओर आयतें बहुत अधिक खाली जगह को कवर न करें और बहुत अधिक ओवरलैप न करें ( जिससे खोज के समय, कम उपवृक्षों को संसाधित करने की आवश्यकता हो)। उदाहरण के लिए, एक कुशल ट्री प्राप्त करने के लिए अवयव ों को सम्मिलित करने का मूल विचार सदैव उस उपट्री में सम्मिलित करना है जिसके बाउंडिंग बॉक्स के कम से कम विस्तार की आवश्यकता होती है। एक बार जब वह पृष्ठ भर जाता है, तो डेटा को दो सेटों में विभाजित किया जाता है, जिनमें से प्रत्येक को न्यूनतम क्षेत्र को कवर करना चाहिए। आर-ट्री के लिए अधिकांश शोध और सुधारों का उद्देश्य ट्री के निर्माण के विधि में सुधार करना है और इसे दो उद्देश्यों में समूहीकृत किया जा सकता है: स्क्रैच से एक कुशल ट्री का निर्माण (जिसे बल्क-लोडिंग के रूप में जाना जाता है) और उपस्थित ट्री पर परिवर्तन करना (सम्मिलन और विलोपन) है।

आर-ट्रीज़ सबसे व्यर्थ स्थिति में अच्छे प्रदर्शन की आश्वासन नहीं देते हैं, किंतु समान्यता: वास्तविक दुनिया के डेटा के साथ अच्छा प्रदर्शन करते हैं।[7] जबकि सैद्धांतिक रुचि अधिक है, आर-ट्री का (थोक-भरा हुआ) प्राथमिकता आर-ट्री संस्करण सबसे व्यर्थ स्थिति में अधिकतम है,[8] किंतु बढ़ती सम्मिश्र्ता के कारण अब तक व्यावहारिक अनुप्रयोगों में इस पर अधिक ध्यान नहीं दिया गया है।

जब डेटा को आर-ट्री में व्यवस्थित किया जाता है, तो एक निश्चित दूरी के आर के निकटतम और के के निकटतम समीप ((किसी भी Lp-नॉर्म के लिए)) सभी बिंदुओं की कुशलता से एक स्थानिक जुड़ाव का उपयोग करके गणना की जा सकती है।[9][10] यह ऐसे प्रश्नों पर आधारित अनेक एल्गोरिदम के लिए लाभदायक है, उदाहरण के लिए स्थानीय आउटलायर फैक्टर डेली-क्लू,[11] डेंसिटी-लिंक-क्लस्टरिंग एक क्लस्टर विश्लेषण एल्गोरिदम है जो प्रकाशिकी एल्गोरिथ्म क्लस्टरिंग की कुशलतापूर्वक गणना करने के लिए समान प्रकार के स्थानिक जुड़ाव के लिए आर-ट्री संरचना का उपयोग करता है।

वेरिएंट

एल्गोरिथम

डेटा लेआउट

आर-ट्री में डेटा को उन पृष्ठों में व्यवस्थित किया जाता है जिनमें प्रविष्टियों की एक परिवर्तनीय संख्या हो सकती है (कुछ पूर्व-निर्धारित अधिकतम तक, और समान्यत: न्यूनतम भरण से ऊपर) नॉन- लसीका नोड के अंदर प्रत्येक प्रविष्टि डेटा के दो टुकड़े संग्रहीत करती है: चाइल्ड नोड की पहचान करने का एक विधि है , और इस चाइल्ड नोड के अंदर सभी प्रविष्टियों का आकार निर्धारक बॉक्स लीफ नोड्स प्रत्येक बच्चे के लिए आवश्यक डेटा संग्रहीत करते हैं अधिकांशतः एक बिंदु या बाउंडिंग बॉक्स बच्चे का प्रतिनिधित्व करता है और बच्चे के लिए एक बाहरी पहचानकर्ता होता है। बिंदु डेटा के लिए, पत्ती प्रविष्टियाँ केवल बिंदु ही हो सकती हैं। बहुभुज डेटा के लिए (जिसमें अधिकांशतः बड़े बहुभुजों के संचयन की आवश्यकता होती है) सामान्य सेटअप ट्री में एक अद्वितीय पहचानकर्ता के साथ बहुभुज के केवल एमबीआर (न्यूनतम बाउंडिंग आयत) को संग्रहीत करना है।

खोजें

श्रेणी खोज में, इनपुट एक खोज आयत (क्वेरी बॉक्स) है। खोजना अधिक सीमा तक बी+ ट्री में खोजने के समान है। खोज ट्री के मूल नोड से प्रारंभ होती है। प्रत्येक आंतरिक नोड में संबंधित चाइल्ड नोड के लिए आयतों और संकेतकों का एक समूह होता है और प्रत्येक लीफ नोड में स्थानिक वस्तुओं के आयत होते हैं (कुछ स्थानिक वस्तु के लिए संकेतक वहां हो सकते हैं)। नोड में प्रत्येक आयत के लिए, यह तय करना होगा कि यह खोज आयत को ओवरलैप करता है या नहीं। यदि हां, तो संबंधित चाइल्ड नोड को भी खोजना होगा। खोज इस प्रकार पुनरावर्ती विधि से की जाती है जब तक कि सभी ओवरलैपिंग नोड्स का पता नहीं लगा लिया जाता। जब एक लीफ नोड तक पहुंच जाता है, तो निहित बाउंडिंग बॉक्स (आयत) का परीक्षण खोज आयत के विरुद्ध किया जाता है और उनके ऑब्जेक्ट (यदि कोई हों) को परिणाम समूह में डाल दिया जाता है यदि वे खोज आयत के अंदर होते हैं।

निकटतम समीप खोज जैसी प्राथमिकता वाली खोज के लिए, क्वेरी में एक बिंदु या आयत होता है। रूट नोड को प्राथमिकता श्रंखला में डाला गया है। जब तक श्रंखला खाली नहीं हो जाती या वांछित संख्या में परिणाम नहीं आ जाते, श्रंखला में निकटतम प्रविष्टि को संसाधित करके खोज जारी रहती है। ट्री नोड्स का विस्तार किया जाता है और उनके बच्चों को पुनः सम्मिलित किया जाता है। श्रंखला में सामने आने पर लीफ प्रविष्टियाँ लौटा दी जाती हैं।[12] इस दृष्टिकोण का उपयोग विभिन्न दूरी आव्यूह `के साथ किया जा सकता है, जिसमें भौगोलिक डेटा के लिए ग्रेट-सर्कल दूरी भी सम्मिलित है।[4]


निवेशन

किसी ऑब्जेक्ट को सम्मिलित करने के लिए, ट्री को रूट नोड से पुनरावर्ती रूप से ट्रैवर्स किया जाता है। प्रत्येक चरण में, वर्तमान निर्देशिका नोड में सभी आयतों की जांच की जाती है, और एक उम्मीदवार को एक अनुमान का उपयोग करके चुना जाता है जैसे कि उस आयत को चुनना जिसमें कम से कम विस्तार की आवश्यकता होती है। खोज तब इस पृष्ठ पर उतरती है, जब तक कि एक लीफ नोड तक नहीं पहुंच जाती। यदि पत्ती नोड भरा हुआ है, तो सम्मिलन करने से पहले इसे विभाजित किया जाना चाहिए। फिर, चूंकि एक विस्तृत खोज बहुत महंगी है, इसलिए नोड को दो भागों में विभाजित करने के लिए एक अनुमान का उपयोग किया जाता है। नए बनाए गए नोड को पिछले स्तर पर जोड़ने से, यह स्तर फिर से ओवरफ्लो हो सकता है, और ये ओवरफ्लो रूट नोड तक फैल सकते हैं; जब यह नोड भी ओवरफ्लो हो जाता है, तो एक नया रूट नोड बन जाता है और ट्री की ऊंचाई बढ़ जाती है।

सम्मिलन उपट्री चुनना

एल्गोरिदम को यह तय करने की आवश्यकता है कि किस उपट्री को सम्मिलित करना है। जब कोई डेटा ऑब्जेक्ट पूरी तरह से एक ही आयत में समाहित होता है, तो विकल्प स्पष्ट होता है। जब अनेक विकल्प या आयतों को बढ़ाने की आवश्यकता होती है, तो विकल्प ट्री के प्रदर्शन पर महत्वपूर्ण प्रभाव डाल सकता है।

ऑब्जेक्ट को उस उपट्री में डाला जाता है जिसे सबसे कम विस्तार की आवश्यकता होती है। एक मिश्रण अनुमानी का प्रयोग सर्वत्र किया जाता है। आगे क्या होता है यह ओवरलैप को कम करने की प्रयाश करता है (संबंधों के स्थिति में, कम से कम विस्तार और फिर सबसे कम क्षेत्र को प्राथमिकता दें); उच्च स्तर पर, यह आर-ट्री के समान व्यवहार करता है, किंतु संबंधों पर फिर से छोटे क्षेत्र वाले उपट्री को प्राथमिकता देता है। आर*-ट्री में आयतों का घटा हुआ ओवरलैप पारंपरिक आर-ट्री की तुलना में प्रमुख लाभों में से एक है।

एक अतिप्रवाहित नोड को विभाजित करना

चूँकि एक नोड की सभी वस्तुओं को दो नोड्स में पुनर्वितरित करने के लिए विकल्पों की एक घातीय संख्या होती है, सर्वोत्तम विभाजन खोजने के लिए एक अनुमान को नियोजित करने की आवश्यकता होती है। उत्कृष्ट आर-ट्री में, गुटमैन ने दो ऐसे अनुमान प्रस्तावित किए, जिन्हें क्वाड्रैटिकस्प्लिट और लीनियरस्प्लिट कहा जाता है। द्विघात विभाजन में, एल्गोरिदम आयतों की जोड़ी की खोज करता है जो एक ही नोड में सबसे व्यर्थ संयोजन है, और उन्हें दो नए समूहों में प्रारंभिक वस्तुओं के रूप में रखता है। इसके बाद यह उस प्रविष्टि की खोज करता है जिसमें किसी एक समूह (क्षेत्र वृद्धि के संदर्भ में) के लिए सबसे शसक्त प्राथमिकता है और इस समूह को तब तक ऑब्जेक्ट आवंटित करता है जब तक कि सभी ऑब्जेक्ट असाइन नहीं किए जाते (न्यूनतम भरण को संतुष्ट करते हुए)।

अन्य विभाजन रणनीतियाँ भी हैं जैसे ग्रीन्स स्प्लिट,[13] आर*-ट्री विभाजन अनुमानी[14] (जो फिर से ओवरलैप को कम करने की प्रयाश करता है, किंतु द्विघात पृष्ठों को भी प्राथमिकता देता है) या एंग और टैन द्वारा प्रस्तावित रैखिक विभाजन एल्गोरिथ्म[15] (जो चूँकि बहुत अनियमित आयत उत्पन्न कर सकता है, जो अनेक वास्तविक विश्व रेंज और विंडो प्रश्नों के लिए कम प्रदर्शन करने वाला है)। अधिक उन्नत विभाजन अनुमानी होने के अतिरिक्त , आर *-ट्री कुछ नोड सदस्यों को फिर से सम्मिलित करके एक नोड को विभाजित करने से बचने की भी प्रयाश करता है, जो कि बी-ट्री ओवरफ्लोिंग नोड्स को संतुलित करने के विधि के समान है। यह ओवरलैप को कम करने और इस प्रकार ट्री के प्रदर्शन को बढ़ाने के लिए भी दिखाया गया था।

अंत में, एक्स-ट्री[16] इसे एक आर*-ट्री वेरिएंट के रूप में देखा जा सकता है जो एक नोड को विभाजित नहीं करने का निर्णय ले सकता है, किंतु सभी अतिरिक्त प्रविष्टियों वाले एक तथाकथित सुपर-नोड का निर्माण कर सकता है, जब इसे एक अच्छा विभाजन नहीं मिलता है (विशेष रूप से उच्च के लिए) आयामी डेटा)।

Effect of different splitting heuristics on a database with US postal districts
  • गुटमैन का द्विघात विभाजन.[2] इस पेड़ के पन्ने बहुत अधिक ओवरलैप होते हैं.

    गुटमैन का द्विघात विभाजन.[2]
    इस पेड़ के पन्ने बहुत अधिक ओवरलैप होते हैं.

  • गुटमैन का रैखिक विभाजन.[2] संरचना और भी ख़राब, लेकिन निर्माण में भी तेज़।

    गुटमैन का रैखिक विभाजन.[2]
    संरचना और भी ख़राब, लेकिन निर्माण में भी तेज़।

  • ग्रीन का विभाजन.[13] गुटमैन की रणनीति की तुलना में पेज बहुत कम ओवरलैप होते हैं।

    ग्रीन का विभाजन.[13] गुटमैन की रणनीति की तुलना में पेज बहुत कम ओवरलैप होते हैं।

  • एंग-टैन रैखिक विभाजन.[15] यह रणनीति कटे हुए पृष्ठ तैयार करती है, जो अधिकांशतः व्यर्थ क्वेरी प्रदर्शन उत्पन्न करते हैं।

    एंग-टैन रैखिक विभाजन.[15]
    यह रणनीति कटे हुए पृष्ठ तैयार करती है, जो अधिकांशतः व्यर्थ क्वेरी प्रदर्शन उत्पन्न करते हैं।

  • R* tree टोपोलॉजिकल विभाजन.[14] चूंकि आर*-ट्री पेज ओवरलैप को कम करने की प्रयास करता है, इसलिए पेज बहुत कम ओवरलैप होते हैं, और पुन: सम्मिलन ट्री को और अधिक अनुकूलित करता है। विभाजित रणनीति द्विघात पृष्ठों को प्राथमिकता देती है, जो सामान्य मानचित्र अनुप्रयोगों के लिए उत्तम प्रदर्शन प्रदान करती है।

    R* tree टोपोलॉजिकल विभाजन.[14]
    चूंकि आर*-ट्री पेज ओवरलैप को कम करने की प्रयास करता है, इसलिए पेज बहुत कम ओवरलैप होते हैं, और पुन: सम्मिलन ट्री को और अधिक अनुकूलित करता है। विभाजित रणनीति द्विघात पृष्ठों को प्राथमिकता देती है, जो सामान्य मानचित्र अनुप्रयोगों के लिए उत्तम प्रदर्शन प्रदान करती है।

  • सॉर्ट-टाइल-रिकर्सिव (एसटीआर) का उपयोग करके थोक में लोड किया गया आर* ट्री। चूंकि आर*-ट्री पेज ओवरलैप को कम करने की प्रयास करता है, इसलिए पेज बहुत कम ओवरलैप होते हैं, और पुन: सम्मिलन ट्री को और अधिक अनुकूलित करता है। विभाजित रणनीति द्विघात पृष्ठों को प्राथमिकता देती है, जो सामान्य मानचित्र अनुप्रयोगों के लिए उत्तम प्रदर्शन प्रदान करती है।

    सॉर्ट-टाइल-रिकर्सिव (एसटीआर) का उपयोग करके थोक में लोड किया गया आर* ट्री।
    चूंकि आर*-ट्री पेज ओवरलैप को कम करने की प्रयास करता है, इसलिए पेज बहुत कम ओवरलैप होते हैं, और पुन: सम्मिलन ट्री को और अधिक अनुकूलित करता है। विभाजित रणनीति द्विघात पृष्ठों को प्राथमिकता देती है, जो सामान्य मानचित्र अनुप्रयोगों के लिए उत्तम प्रदर्शन प्रदान करती है।

  • एम-ट्री आर-ट्री के समान हैं, लेकिन नेस्टेड गोलाकार पृष्ठों का उपयोग करते हैं. चूँकि, इन पृष्ठों को विभाजित करना अधिक सम्मिश्र है और पृष्ठ सामान्यतः बहुत अधिक ओवरलैप होते हैं।

    एम-ट्री आर-ट्री के समान हैं, लेकिन नेस्टेड गोलाकार पृष्ठों का उपयोग करते हैं.
    चूँकि, इन पृष्ठों को विभाजित करना अधिक सम्मिश्र है और पृष्ठ सामान्यतः बहुत अधिक ओवरलैप होते हैं।

विलोपन

किसी पृष्ठ से किसी प्रविष्टि को हटाने के लिए मूल पृष्ठों के बाउंडिंग आयतों को अद्यतन करने की आवश्यकता हो सकती है। चूँकि जब कोई पृष्ठ कम भरा होता है, तो वह अपने समिपों के साथ संतुलित नहीं होगा। इसके अतिरिक्त , पेज को विघटित कर दिया जाएगा और उसके सभी बच्चों (जो कि केवल लीफ ऑब्जेक्ट ही नहीं, किंतु सबट्री भी हो सकते हैं) को फिर से सम्मिलित कर दिया जाएगा। यदि इस प्रक्रिया के समय रूट नोड में एक भी अवय है, तो ट्री की ऊंचाई कम हो सकती है।

थोक-लोडिंग

  • निकटतम-एक्स: वस्तुओं को उनके पहले निर्देशांक (एक्स) के अनुसार क्रमबद्ध किया जाता है और फिर वांछित आकार के पृष्ठों में विभाजित किया जाता है।
  • पैक्ड हिल्बर्ट आर-ट्री: निकटतम-एक्स की भिन्नता, किंतु एक्स समन्वय का उपयोग करने के अतिरिक्त आयत के केंद्र के हिल्बर्ट मान का उपयोग करके सॉर्ट करना है। इसकी कोई आश्वासन नहीं है कि पेज ओवरलैप नहीं होंगे।
  • सॉर्ट-टाइल-रिकर्सिव (एसटीआर):[17] निकटतम-एक्स का एक और रूपांतर, जो आवश्यक पत्तियों की कुल संख्या का अनुमान लगाता है , इसे के रूप में प्राप्त करने के लिए प्रत्येक आयाम में आवश्यक विभाजन कारक, फिर 1-आयामी सॉर्टिंग का उपयोग करके प्रत्येक आयाम को क्रमिक रूप से समान आकार के विभाजन में विभाजित करता है। परिणामी पृष्ठ, यदि वे एक से अधिक पृष्ठों पर अधिकृत करते हैं, तो उसी एल्गोरिथ्म का उपयोग करके फिर से थोक में लोड किए जाते हैं। बिंदु डेटा के लिए, लीफ़ नोड्स ओवरलैप नहीं होंगे, और डेटा स्थान को लगभग समान आकार के पृष्ठों में "टाइल" करेंगे।
  • ओवरलैप मिनिमाइजिंग टॉप-डाउन (ओएमटी):[18] टॉप-डाउन दृष्टिकोण का उपयोग करके एसटीआर में सुधार जो स्लाइस के बीच ओवरलैप को कम करता है और क्वेरी प्रदर्शन में सुधार करता है।
  • प्राथमिकता आर-वृक्ष

यह भी देखें

संदर्भ

  1. ↑ https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf[bare URL PDF]
  2. ↑ 2.0 2.1 2.2 Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial Searching" (PDF). Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84. p. 47. doi:10.1145/602259.602266. ISBN 978-0897911283. S2CID 876601.
  3. ↑ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). R-Trees: Theory and Applications. Springer. ISBN 978-1-85233-977-7. Retrieved 8 October 2011.
  4. ↑ 4.0 4.1 Schubert, E.; Zimek, A.; Kriegel, H. P. (2013). "Geodetic Distance Queries on R-Trees for Indexing Geographic Data". स्थानिक और लौकिक डेटाबेस में प्रगति. Lecture Notes in Computer Science. Vol. 8098. p. 146. doi:10.1007/978-3-642-40235-7_9. ISBN 978-3-642-40234-0.
  5. ↑ Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). "Nearest neighbor queries". Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.
  6. ↑ Mengbai Xiao, Hao Wang, Liang Geng, Rubao Lee, and Xiaodong Zhang (2022). "क्लस्टरों पर आर-ट्री के लिए एक आरडीएमए-सक्षम इन-मेमोरी कंप्यूटिंग प्लेटफ़ॉर्म". ACM Transactions on Spatial Algorithms and Systems. pp. 1–26. doi:10.1145/3503513.{{cite conference}}: CS1 maint: multiple names: authors list (link)
  7. ↑ Hwang, S.; Kwon, K.; Cha, S. K.; Lee, B. S. (2003). "Performance Evaluation of Main-Memory R-tree Variants". स्थानिक और लौकिक डेटाबेस में प्रगति. Lecture Notes in Computer Science. Vol. 2750. pp. 10. doi:10.1007/978-3-540-45072-6_2. ISBN 978-3-540-40535-1.
  8. ↑ Arge, L.; De Berg, M.; Haverkort, H. J.; Yi, K. (2004). "The Priority R-tree" (PDF). Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04. p. 347. doi:10.1145/1007568.1007608. ISBN 978-1581138597. S2CID 6817500.
  9. ↑ Brinkhoff, T.; Kriegel, H. P.; Seeger, B. (1993). "आर-पेड़ों का उपयोग करके स्थानिक जोड़ों का कुशल प्रसंस्करण". ACM SIGMOD Record. 22 (2): 237. CiteSeerX 10.1.1.72.4514. doi:10.1145/170036.170075.
  10. ↑ Böhm, Christian; Krebs, Florian (2003-09-01). के-निकटतम पड़ोसी द्वारा केडीडी अनुप्रयोगों का समर्थन करना. pp. 504–516. CiteSeerX 10.1.1.71.454. doi:10.1007/978-3-540-45227-0_50. ISBN 9783540408062. {{cite book}}: |journal= ignored (help)
  11. ↑ Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". In Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 3918. Springer. pp. 119–128. doi:10.1007/11731139_16.
  12. ↑ Kuan, J.; Lewis, P. (1997). "Fast k nearest neighbour search for R-tree family". Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237). p. 924. doi:10.1109/ICICS.1997.652114. ISBN 0-7803-3676-3.
  13. ↑ 13.0 13.1 Greene, D. (1989). "An implementation and performance analysis of spatial data access methods". [1989] Proceedings. Fifth International Conference on Data Engineering. pp. 606–615. doi:10.1109/ICDE.1989.47268. ISBN 978-0-8186-1915-1. S2CID 7957624.
  14. ↑ 14.0 14.1 Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: an efficient and robust access method for points and rectangles" (PDF). Proceedings of the 1990 ACM SIGMOD international conference on Management of data – SIGMOD '90. p. 322. CiteSeerX 10.1.1.129.3731. doi:10.1145/93597.98741. ISBN 978-0897913652. S2CID 11567855.
  15. ↑ 15.0 15.1 Ang, C. H.; Tan, T. C. (1997). "आर-पेड़ों के लिए नया रैखिक नोड विभाजन एल्गोरिदम". In Scholl, Michel; Voisard, Agnès (eds.). Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997. Lecture Notes in Computer Science. Vol. 1262. Springer. pp. 337–349. doi:10.1007/3-540-63238-7_38.
  16. ↑ Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter (1996). "The X-Tree: An Index Structure for High-Dimensional Data". Proceedings of the 22nd VLDB Conference. Mumbai, India: 28–39.
  17. ↑ Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (February 1997). "STR: A Simple and Efficient Algorithm for R-Tree Packing". {{cite journal}}: Cite journal requires |journal= (help)
  18. ↑ Lee, Taewon; Lee, Sukho (June 2003). "OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree" (PDF). {{cite journal}}: Cite journal requires |journal= (help)


बाहरी संबंध

  • Media related to R-tree at Wikimedia Commons
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=आर-ट्री&oldid=235789’