आर-ट्री: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Data structures used in spatial indexing}} {{About|the data structure|the type of metric space|Real tree}} {{More citations needed|date=May 2023}} {{Infobo...")
 
No edit summary
Line 1: Line 1:
{{Short description|Data structures used in spatial indexing}}
{{Short description|Data structures used in spatial indexing}}
{{About|the data structure|the type of metric space|Real tree}}
{{About|the data structure|the type of metric space|Real tree}}
{{More citations needed|date=May 2023}}
{{Infobox data structure
{{Infobox data structure
|name=R-tree
|name=R-tree
Line 18: 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>{{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> ग्रेट-सर्कल दूरी सहित विभिन्न दूरी मेट्रिक्स के लिए।<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>
[[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>{{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> ग्रेट-सर्कल दूरी सहित विभिन्न दूरी मेट्रिक्स के लिए।<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>




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


[[ बी-वृक्ष ]] के समान, आर-ट्री भी एक संतुलित खोज ट्री है (इसलिए सभी लीफ नोड्स समान गहराई पर हैं), डेटा को पृष्ठों में व्यवस्थित करता है, और डिस्क पर भंडारण के लिए डिज़ाइन किया गया है (जैसा कि [[डेटाबेस]] में उपयोग किया जाता है)। प्रत्येक पृष्ठ में अधिकतम संख्या में प्रविष्टियाँ हो सकती हैं, जिन्हें अक्सर इस रूप में दर्शाया जाता है <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> यह दृष्टिकोण तेजी से बड़े अनुप्रयोगों के लिए स्केलेबल है और आर-ट्री के लिए उच्च थ्रूपुट और कम विलंबता प्रदर्शन प्राप्त करता है।
Line 60: Line 59:


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


=== खोजें ===
=== खोजें ===
Line 97: Line 96:
=== विलोपन ===
=== विलोपन ===
किसी पृष्ठ से किसी प्रविष्टि को हटाने के लिए मूल पृष्ठों के बाउंडिंग आयतों को अद्यतन करने की आवश्यकता हो सकती है। हालाँकि, जब कोई पृष्ठ कम भरा होता है, तो वह अपने पड़ोसियों के साथ संतुलित नहीं होगा। इसके बजाय, पेज को विघटित कर दिया जाएगा और उसके सभी बच्चों (जो कि केवल लीफ ऑब्जेक्ट ही नहीं, बल्कि सबट्री भी हो सकते हैं) को फिर से सम्मिलित कर दिया जाएगा। यदि इस प्रक्रिया के दौरान रूट नोड में एक भी तत्व है, तो पेड़ की ऊंचाई कम हो सकती है।
किसी पृष्ठ से किसी प्रविष्टि को हटाने के लिए मूल पृष्ठों के बाउंडिंग आयतों को अद्यतन करने की आवश्यकता हो सकती है। हालाँकि, जब कोई पृष्ठ कम भरा होता है, तो वह अपने पड़ोसियों के साथ संतुलित नहीं होगा। इसके बजाय, पेज को विघटित कर दिया जाएगा और उसके सभी बच्चों (जो कि केवल लीफ ऑब्जेक्ट ही नहीं, बल्कि सबट्री भी हो सकते हैं) को फिर से सम्मिलित कर दिया जाएगा। यदि इस प्रक्रिया के दौरान रूट नोड में एक भी तत्व है, तो पेड़ की ऊंचाई कम हो सकती है।
{{Expand section|date=October 2011}}


=== थोक-लोडिंग ===
=== थोक-लोडिंग ===
Line 107: Line 104:
* ओवरलैप मिनिमाइजिंग टॉप-डाउन (ओएमटी):<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> टॉप-डाउन दृष्टिकोण का उपयोग करके एसटीआर में सुधार जो स्लाइस के बीच ओवरलैप को कम करता है और क्वेरी प्रदर्शन में सुधार करता है।
* प्राथमिकता आर-वृक्ष
* प्राथमिकता आर-वृक्ष
{{Expand section|date=June 2008}}


== यह भी देखें ==
== यह भी देखें ==
Line 125: Line 120:
== बाहरी संबंध ==
== बाहरी संबंध ==
* {{commons category-inline|R-tree}}
* {{commons category-inline|R-tree}}
{{CS-Trees}}
{{Data structures}}


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

Revision as of 07:50, 17 July 2023

This article is about the data structure. For the type of metric space, see Real tree.
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)
File:R-tree.svg
2डी आयतों के लिए आर-ट्री का सरल उदाहरण
File:RTree-Visualization-3D.svg
ELKI का उपयोग करके 3D बिंदुओं के लिए R*-ट्री का विज़ुअलाइज़ेशन (क्यूब्स निर्देशिका पृष्ठ हैं)

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


आर-वृक्ष विचार

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

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

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

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

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

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

वेरिएंट

एल्गोरिथम

डेटा लेआउट

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

खोजें

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

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


निवेशन

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

सम्मिलन उपवृक्ष चुनना

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

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

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

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

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

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

Effect of different splitting heuristics on a database with US postal districts
  • R-tree with Guttman's quadratic split.png

    Guttman's quadratic split.[2]
    Pages in this tree overlap a lot.

  • R-tree built with Guttman's linear split.png

    Guttman's linear split.[2]
    Even worse structure, but also faster to construct.

  • R-tree built with Greenes Split.png

    Greene's split.[13] Pages overlap much less than with Guttman's strategy.

  • R-tree built with Ang-Tan linear split.png

    Ang-Tan linear split.[15]
    This strategy produces sliced pages, which often yield bad query performance.

  • R*-tree built using topological split.png

    R* tree topological split.[14]
    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.

  • R*-tree bulk loaded with sort-tile-recursive.png

    Bulk loaded R* tree using Sort-Tile-Recursive (STR).
    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.

  • M-tree built with MMRad split.png

    M-trees are similar to the R-tree, but use nested spherical pages.
    Splitting these pages is, however, much more complicated and pages usually overlap much more.

विलोपन

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

थोक-लोडिंग

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