درخت مستطیلی

درخت مستطيلي

درخت مستطیلی (به انگلیسی: R-Tree) داده ساختاری درختی است که در روش‌های دسترسی مکانی مانند فهرست کردن اطلاعات چندبعدی همچون مختصات جغرافیایی، مستطیل‌ها یا چندضلعی‌ها استفاده می‌شود. درخت مستطیلی توسط آنتونین گاتمَن (Antonin Guttman) در سال 1984^[۱] پیشنهاد شد و کاربردهای مختلفی در زمینه‌های نظری و کاربردی بدست آورد.^[۲]یکی از کاربردهای معمول درخت مستطیلی می‌تواند ذخیره شیء‌های مکانی مانند مکان رستوران‌ها یا چند ضلعی‌هایی که نقشه‌های معمولی از آن‌ها ساخته می‌شوند: خیابان‌ها، ساختمان‌ها، مرز دریاچه‌ها، خطوط ساحلی و غیره، و سپس یافتن سریع پاسخ سوال‌هایی مانند "تمام موزه‌هایی که در ۲ کیلومتری مکان من هستند را پیدا کن"،"بازیابی تمام جاده‌ها تا ۲ کیلومتری اطراف من (برای نشان دادن در سامانه راه یابی)" یا "نزدیک‌ترین پمپ بنزین را پیدا کن"، باشد.

ایده درخت مستطیلی

ایده اصلی این داده ساختار این است که اشیاء نزدیک هم را در یک گروه قرار دهیم و آن‌ها را با کوچکترین مستطیلی که آن‌ها را احاطه می‌کند در سطح بالایی درخت نشان دهیم؛ R در "درخت R" از اول کلمه rectangle گرفته شده‌است. از آن جایی که همه اشیاء در مستطیل احاطه‌کننده قرار می‌گیرند، یک جستجو که تداخلی با مستطیل احاطه‌کننده ندارد پس نمی‌تواند تداخلی با هیچ یک از اشیاء داخل آن داشته باشد. در سطح برگ هر مستطیل نشان دهده یک شیء هست؛ در سطوح بالاتر این تعداد افزایش پیدا می‌کند. این مورد را همچنین می‌توان به صورت یک تقریب بزرگِ افزاینده از مجموعه داده دید. مشابه با درخت B، درخت مستطیلی هم یک درخت جستجو متوازن است (پس همهٔ برگ‌ها در یک ارتفاع هستند)، داده‌ها را در صفحه سازمان دهی می‌کند، و برای ذخیره بر روی دیسک طراحی شده‌است. هر صفحه می‌تواند حاوی یک مقدار حداکثری از ورودی‌ها باشد که معمولاً با M نشان داده می‌شود. همچنین یک مقدار حداقلی هم تضمین می‌شود (بجز گره ریشه)، اگر چه بهترین عملکرد با حداقل پر شدن ۳۰٪ تا ۴۰٪ حداکثر مقدار داده‌ها، تجربه شده‌است (درخت B پر شدن ۵۰٪ و درخت *B پر شدن ۶۶٪ صفحه را ضمانت می‌کند). دلیل این مورد، پیچیده تر بودن متوازن سازی برای داده‌های مکانی در برابر داده‌های خطی ذخیره شده در درخت B است. مانند اکثر درخت‌ها الگوریتم‌های جستجو (برای مثال تلاقی، حاوی بودن، جستجو نزدیکترین همسایه) نسبتاً ساده هستند. ایده اصلی استفاده کردن از مستطیل احاطه‌کننده برای تصمیم گیری در مورد اینکه داخل یک زیر درخت جستجو شود یا نه، است. به این ترتیب اکثر گره‌ها در طول جستجو اصلاً دیده نمی‌شوند. این مورد باعث می‌شود درخت مستطیلی برای مجموعه داده‌های بزرگ و پایگاه‌های داده مناسب باشد؛ جایی که کل درخت در حافظه جا نمی‌شود و گره‌ها در هنگام نیاز به حافظه منتقل می‌شوند. سختی اصلی طراحی درخت مستطیلی این است که از یک طرف درخت باید متوازن باشد (برگ‌ها در یک ارتفاع باشند) و از طرف دیگر مستطیل‌ها فضای خالی زیادی را پوشش ندهند و زیاد هم پوشانی نداشته باشند (تا در هنگام جستجو نیاز به بررسی تعداد کمتری زیردرخت باشد). برای مثال، ایده اصلی برای اضافه کردن داده‌ها برای بدست آمدن یک درخت بهینه این است که همیشه به زیردرختی که نیاز به کمترین بزرگ شدن مستطیل احاطه‌کننده‌اش دارد، اضافه کنیم. وقتی آن صفحه پر شد، داده‌ها به دو مجموعه که هر کدام مقدار کمینه‌ای مساحت را پوشش می‌دهند، تقسیم می‌شوند. هدف اکثر تحقیقات و بهبودها برای درخت R، بهبود نحوه ساخت درخت است و می‌توان آن‌ها را به دو بخش تقسیم کرد: ساخت یک درخت بهینه از ابتدا (بارگذاری توده‌ای) و ایجاد تغییرات بر روی یک درخت موجود (حذف و اضافه). درخت‌های مستطیلی کارایی خوب برای بدترین حالت را تضمین نمی‌کنند ولی عموماً برای داده‌های واقعی خوب کار می‌کنند.^[۳]از جنبه نظری درخت مستطیلی اولویت (بارگذاری توده‌ای شده) از انواع درخت مستطیلی در بدترین حالت بهینه است^[۴]، ولی به دلیل زیاد شدن پیچیدگی توجه زیادی در کاربردهای عملی به آن نشده‌است. وقتی داده‌ها در درخت مستطیلی سازمان دهی شده‌اند، k نزدیکترین همسایه‌های (برای هر LP-Norm) همه نقاط می‌تواند به صورت بهینه با استفاده از یک پیوند زدن مکانی محاسبه شود.^[۵]این مورد برای بسیاری از الگوریتم‌های مبتنی بر k نزدیک‌ترین همسایه‌ها، مفید است، برای مثال الگوریتم عامل محلی پرت.^[۶] "تراکم-اتصال-دسته بندی کردن" یک الگوریتم آنالیز خوشه‌ای است که از ساختار درخت مستطیلی برای انواع مشابه اتصال مکانی استفاده می‌کند تا به صورت بهینه یک دسته‌بندی OPTICS را محاسبه کند.

انواع

• درخت مستطیلی*
• درخت مستطیلی+
• درخت مستطیلی هیلبرت
• درخت X

الگوریتم‌ها

ساختار داده

داده‌ها در درخت مستطیلی در چند صفحه سازمان دهی می‌شوند، که می‌توانند شامل تعداد متغیری مدخل باشند (حداکثر تا تعداد یک مقدار از قبل تعیین شده و معمولاً بیشتر از یک مقدار حداقلی). هر مدخل درون یک گره غیر برگ دو قطعه اطلاعات نگهداری می‌کند: یک راه برای شناسایی گره فرزند. و مستطیل احاطه‌کننده تمام مدخل‌های درون این گره فرزند. گره‌های برگ اطلاعات مورد نیاز برای هر فرزند را نگه می‌دارند، معمولاً یک نقطه یا مستطیل احاطه‌کننده معرّف فرزند و یک شناسه خارجی برای فرزند. برای داده نقطه‌ای، مدخل‌های برگ می‌تواند فقط خود نقطه‌ها باشد. برای داده چندضلعی (که معمولاً نیازمند ذخیره چند ضلعی‌های بزرگ می‌باشد) راه معمول ذخیره فقط مستطیل احاطه‌کننده کمینه (MBR-minimum bounding rectangle) چند ضلعی به همراه یک شناسه یکتا در درخت، است.

جستجو

جستجو در درخت مستطیلی شبیه جستجو در درخت بی است. ورودی یک مستطیل (جعبهٔ جستجو) است. جستجو از ریشهٔ درخت شروع می‌شود. هر گرهٔ داخلی شامل مجموعه‌ای از مستطیل‌ها و اشاره گر به گره‌های فرزند است و هر برگ شامل مستطیلی از اشیای مکانی است (می‌تواند شامل اشیای مکانی هم باشد). به ازای هر گره مستطیل متناظر آن با ورودی مقایسه می‌شود، در صورتی همپوشانی، گرهٔ فرزند هم جستجو می‌شود. جستجو به صورت بازگشتی تا زمانی ادامه پیدا می‌کند که تمام گره‌های دارای هم پوشانی با ورودی پیمایش شوند. اگر گره مورد بررسی برگ باشد، مستطیل دربرگیرنده آن با ورودی مقایسه می‌شود و اشیای موجود در آن (در صورت وجود) که در مستطیل ورودی قرار دارند به جواب اضافه می‌شوند.

افزودن عنصر

برای افزودن عنصر جدید درخت با شروع از ریشه به صورت بازگشتی پیمایش می‌شود. در هر سطح تمام مستطیل‌های این سطح بررسی می‌شوند و نماینده با استفاده از الگوریتم اکتشافی (مثلاً انتخاب الگوریتمی که کمترین گسترش را نیاز دارد) انتخاب می‌شود. سپس جستجو به صفحهٔ انتخابی تقلیل پیدا می‌کند و این روند تا رسیدن به برگ ادامه می‌یابد. اگر برگ پر باشد قبل از افزودن عنصر جدید باید به دو گره تقسیم شود. افزودن گره‌ای که تازه ایجاد شده‌است به سطح قبلی می‌تواند منجر به سرریزی در سطح فعلی شود. در بدترین حالت این سرریز شدن‌ها می‌توانند تا ریشه ادامه پیدا کنند. در این حالت یک ریشهٔ جدید ایجاد می‌شود و ارتفاع درخت یک واحد افزایش می‌یابد.

انتخاب زیردرخت

در هر مرحله الگوریتم افزودن عنصر جدید باید تصمیم گرفته شود که شئ جدید در کدام زیردرخت قرار داده شود. زمانی که شئ به‌طور کامل داخل یک مستطیل قرار می‌گیرد انتخاب واضح است؛ اما زمانی که چندین گزینه وجود دارد، انتخاب زیردرخت می‌تواند بر کارآیی الگوریتم تأثیر زیادی داشته باشد. در درخت مستطیلی کلاسیک (به انگلیسی: Classic R-Tree) اشیاء در زیردرختی قرار داده می‌شوند که کمترین گسترش را نیاز دارد؛ اما در مدل‌های پشرفته تر (مثل درخت مستطیلی ستاره‌ای (به انگلیسی: R*-Tree)) روشی ابتکاری به کار گرفته می‌شود. در سطح برگ‌ها سعی می‌شودهمپوشانی‌ها تا حد امکان کمینه گردند. در سطوح بالاتر الگوریتم همانند روش کلاسیک عمل می‌کند. در صورتی که میزان گسترش مورد نیاز برای دو زیردرخت مساوی باشد، زیردرخت با مساخت کمتر انتخاب می‌شود. کاهش یافتن همپوشانی‌ها در مدل پیشرفته یکی از مزیت‌های اساسی آن نسبت به مدل کلاسیک است.

تقسیم گرهٔ پرشده

از آن جایی که زمان بررسی تمامی حالات تقسیم عناصر یک گره به دو گرهٔ مجزا به منظور یافتن حالت بهینه نمایی است باید الگوریتمی ابتکاری برای یافتن بهترین تقسیم به کار گرفته شود. در درخت مستطیلی کلاسیک، گاتمَن الگوریتم‌های تقسیم خطی و درجه دو را پیشنهاد کرده‌است. در الگوریتم تقسیم درجهٔ دو به دنبال مستطیل‌هایی می‌گردیم که در بدترین حالت در یک گره قرار می‌گیرند. این دو گره را گرهٔ حاصل از تقسیم گرهٔ اصلی در نظر می‌گیریم. سپس از بین مستطیل‌های باقی‌مانده، مستطیلی که بیشترین اولویت برای اضافه شدن به یکی از گره‌ها را دارد (یعنی افزودن مستطیل به گره منجر به کمترین افزایش مساحت می‌شود) به گرهٔ مربوطه اضافه می‌کنیم. این روند را تا زمانی ادامه می‌دهیم که تمام اشیاء به گره‌ها نسبت داده شوند. استراتژی‌های تقسیم دیگری مثل Greene's Split^[۷] ، روش ابتکاری تقسیم درخت مستطیلی ستاره‌ای^[۸] یا روش تقسیم خطی پیشنهاد شده توسط Ang و Tan^[۹] (هرچند می‌تواند مستطیل‌های غیرطبیعی ایجاد کند که برای بسیاری از پرس و جوهای جهان واقعی کارآمد نیستند) برای تقسیم پیشنهاد شده‌است. علاوه برداشتن الگوریتم ابتکاری پیشرفته برای تقسیم گره‌ها، درخت مستطیلی ستاره سعی می‌کند با تکرار کردن عناصر موجود در یک گره از تقسیم شدن آن جلوگیری کند (شبیه روشی که برای گره‌های پر شده در درخت بی مورد استفاده قرار می‌گیرد). با این تکنیک هم پوشانی کاهش و کارآیی افزایش می‌یابد. درخت ایکس (به انگلیسی: X-Tree)^[۱۰] درختی مستطیل ستاره‌ای است که وقتی نمی‌تواند تقسیم مناسبی پیدا کند با جای تقسیم، گره‌ای جدید (موسوم به ابرگره) ایجاد می‌کند و تمام عناصر اضافی را در آن قرار می‌دهد.

حذف

حذف کردن یک عنصر از صفحه ممکن است نیازمند به روزرسانی مستطیل در برگیرندهٔ صفحهٔ پدر آن باشد. از آن جایی که وقتی یک صفحه پر نشده‌است، نمی‌تواند با همسایه‌هایش در تعادل باشد، صفحه حذف می‌شود تمام فرزندانش (که می‌توانند زیر درخت یا برگ باشند) دوباره به درخت اضافه می‌شوند. در طی این فرایند اگر ریشهٔ درخت تنها یک فرزند داشته باشد، ارتفاع درخت یک واحد کم می‌شود.

منابع

1. Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial Searching". Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. p. 47. doi:10.1145/602259.602266. ISBN 0897911288
2. Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). R-Trees: Theory and Applications. Springer. ISBN 978-1-85233-977-7. Retrieved 8 October 2011.
3. Hwang, S. ; Kwon, K. ; Cha, S. K. ; Lee, B. S. (2003). "Performance Evaluation of Main-Memory R-tree Variants". Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science 2750. p. 10. doi:10.1007/978-3-540-45072-6_2. شابک ‎۹۷۸−۳−۵۴۰−۴۰۵۳۵−۱.
4. Arge, L. ; De Berg, M. ; Haverkort, H. J. ; Yi, K. (2004). "The Priority R-tree". Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04. p. 347. doi:10.1145/1007568.1007608. ISBN 1581138598
5. Brinkhoff, T. ; Kriegel, H. P. ; Seeger, B. (1993). "Efficient processing of spatial joins using R-trees". ACM SIGMOD Record 22 (2): 237. doi:10.1145/170036.170075
6. Achtert, E. ; Böhm, C. ; Kröger, P. (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". LNCS: Advances in Knowledge Discovery and Data Mining. Lecture Notes in Computer Science 3918: 119–128. doi:10.1007/11731139_16. شابک ‎۹۷۸−۳−۵۴۰−۳۳۲۰۶−۰
7. Greene, D (۱۹۸۹)، "An implementation and performance analysis of spatial data access methods"، Fifth International Conference on Data Engineering
8. Beckmann, N (۱۹۹۰)، "The R*-tree: an efficient and robust access method for points and rectangles"، ACM SIGMOD international conference on Management of data - SIGMOD
9. Ang, C. H. ; Tan, T. C (۱۹۹۷)، "New linear node splitting algorithm for R-trees"، Proceedings of the 5th International Symposium on Advances in Spatial Databasesنگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده)
10. Berchtold, Stefan; Keim, Daniel A. ; Kriegel, Hans-Peter (۱۹۹۶)، "The X-Tree: An Index Structure for High-Dimensional Data"، Proceedings of the 22nd VLDB Conference (Mumbai, India): 28–39نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (رده)

پیوند به بیرون