आर-ट्री: Difference between revisions

[[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%)। इसका कारण बी-ट्रीों में संग्रहीत रैखिक डेटा के विपरीत स्थानिक डेटा के लिए आवश्यक अधिक जटिल संतुलन है।

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

जब डेटा को आर-ट्री में व्यवस्थित किया जाता है, तो एक निश्चित दूरी के आर के निकटतम और के के निकटतम समीप ((किसी भी L^p-नॉर्म के लिए)) सभी बिंदुओं की कुशलता से एक स्थानिक जुड़ाव का उपयोग करके गणना की जा सकती है।<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

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

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

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

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

|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 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 Greenes Split.png|Greene's split.<ref name="greene" /> Pages overlap much less than with Guttman's strategy.

|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 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 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: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