داده‌های حجیم: درخت مستطیلی و پرس‌و‌جوهای شامل شدن نقطه

این در مقاله بود اما در اسلایدها نبود.

http://www.cs.au.dk/~large/ioS13/Lecture6.pdf

R-tree

ساختار این داده‌ساختار شبیه B-tree است فقط در هر گره مستطیل نگه می‌داریم. برگ‌ها که مستطیل‌های ورودی هستند و گره‌های میانی کوچکترین مستطیل محیطی مستطیل‌های زیردرخت آن گره هستند.

برای پرس‌و‌جو از ریشه چک می‌کنیم که نقطه در کدام مستطیل می‌افتد.

حالا سوالی که پیش میاد این است که ترتیب مستطیل‌ها را چطور انتخاب کنیم که کمترین زمان را ببرد. چیزی که می‌دانیم این است که هر چه مستطیل‌ها کوچکتر باشند، عمق کمتری باید پایین برویم پس بهتر است.

سه ایده برای دسته بندی مستطیل‌ها در گره‌های میانی داریم:

- مینیمم کردن مساحت مستطیل محیطی

- مینیمم کردن محیط مستطیل محیطی

- مینیمم کردن تقاطع مستطیل‌ها

* اضافه کردن مستطیل:

مستطیل را به آن مستطیلی اضافه کنید که بعد از این کار مساحتش کمتر از همه زیاد می‌شود. به طور بازگشتی ادامه بدهید.

در برگ اگر جا بود اضافه کنید وگرنه split انجام بدهید. (سعی کنید مساحت مینیمم شود.)

(با این کار به گره یک عمق بالاتر یک گره اضافه می‌شود.)

* حذف کردن مستطیل:

حذف می‌کنیم اگر خیلی مستطیل محیطی خالی بود آن را حذف می‌کنیم و به بقیه اضافه می‌کنیم.

...

PR-tree:

مستطیل‌های با بیشترین و کمترین مختصات را در برگ‌ها می‌گذاریم. بقیه را مثل kd-tree تقسیم می‌کنیم.

قابل تعمیم به d بعد است.

--------------------------------------

پیدا کردن پاره‌خط‌های متقاطع با فرض پاره‌خط‌های موازی محورهای مختصات: (در مدل IO)

الگوریتم جاروب معمولی حتی با B-tree هم زمان O(N log_B N+T/B) دارد که خوب نیست. (به خاطر ضریب N)

راه حل: الگوریتم جاروب توزیع شده:

صفحه را به M/B-1 نوار (slab) تجزیه کنید که هر کدام O(N/(M/B)) تا نقطه انتهایی دارند.

در هر نوار از بالا به پایین عمودی جاروب کنید و پاره‌خط‌های متقاطع را به دست بیاورید.

آنهایی که در بیشتر از یک نوار تقاطع دارند را توزیع کنید.

در هر نوار به صورت بازگشتی مسأله را حل کنید.

کاربرد: پیدا کردن مستطیل‌های متقاطع با فرض مستطیل‌های با اضلاع موازی محورهای مختصات