עץ R
פעולות > שאילתות חיפוש מרחביות > צירוף מרחבי

פעולות חיפוש מסוג אחר הן פעולות שמצריכות סריקה חוזרת של העצמים שבמרחב. פעולה נפוצה כזו היא פעולת חיפוש של צירוף מרחבי (spatial join) עם פרדיקט של חיתוך שמוגדרת בצורה הבאה: עבור שני יחסים שמכילים קבוצות של עצמים במרחב, הצירוף המרחבי שלהם הוא קבוצת כל העצמים שחופפים בין הקבוצות. פעולה זו היא למעשה הרחבה של חיפוש תחום, כך שקלט החיפוש שהכיל מלבן יחיד יכיל קבוצה של מלבנים.
אלגוריתם נאיבי לצירוף מרחבי כזה הוא אלגוריתם שעושה שימוש בלולאות מקוננות והוא לא יעיל במיוחד בסיבוכיות זמן ריצה שלו עבור קבוצות גדולות של עצמים. אלגוריתמים שונים שמבוססים על עץ R ועל וריאציות שלו הוצעו כדי לייעל את הפעולה.
אחד האלגוריתמים הראשונים שמטרתו לבצע צירוף מרחבי בין שני יחסים שמיוצגים בשני עצי R עם גבהים שונים הוצע על ידי Brinkhoff,‏ Kriegel,‏ ו-Seeger ב-1993. אלגוריתם זה מכונה לפעמים אלגוריתם RJ ‏(R-tree Join) או אלגוריתם התאמת עץ, ופועל בצורה של חיפוש לעומק:
תחילה נעשה ניסיון לצמצם את מרחב החיפוש על ידי חישוב השטח החופף בין המלבנים שמייצגים את השורשים של העצים ופסילת צומתי הבנים שלא יכולים לחפוף לשטח זה.
לאחר מכן נבנית רשימה ממויינת של מלבני הבנים שנשארו בהתבסס על סדר עולה של ערכי קואורדינטה באחת הקודקודים - למשל על פי ערך ה-x בקודקוד השמאלי התחתון שלהם. על רשימה זו מתבצע מעבר באלגוריתם סריקת מישור (plane sweep algorithm) תוך עצירה בנקודת ה-x הממויינת של כל מלבן, ומציאת זוגות מתאימים של מלבנים משני העצים שחופפים זה לזה.
בסריקה נעשה שימוש במנגנון שמטרתו להצמיד את הזוגות שאליהם שייך המלבן שיש לו את הכמות הגדולה ביותר של חפיפות עם מלבנים אחרים. בכך מנסים לאפשר למלבן שמשתתף ביותר פעולות יחסית למלבנים האחרים 'להינעץ' בזיכרון הפנימי, והדבר מייעל את הביצועים של האלגוריתם.
עבור כל זוג מלבנים חופפים האלגוריתם מופעל בצורה רקורסיבית על שני תתי העצים שהם מייצגים, וכך הלאה עד שאחד מתתי העצים הוא עלה. במצב כזה עוברים על כל המלבנים שמוצבעים באותו עלה, ומשתמשים בהם כקלטים לפעולות חיפוש של מלבן בתת-העץ השני. עצמים שנמצאה ביניהם חפיפה מתווספים לקבוצת הערכים של תוצאת הצירוף המרחבי.
למצבים בהם רק אחד מהיחסים מיוצג בעץ R, הוצע אלגוריתם לבניית עץ מתאים ליחס השני על ידי Lo ו-Ravishankar בשנת 1994. מבנה הנתונים הנוסף שמוגדר עבור היחס השני הוא עץ שתול (seeded tree) והוא מתבסס על ערכים מהעץ R שכבר נתון. הרעיון בבנייה כזו הוא לצמצם את כמות החפיפות שיימצאו בין זוגות מלבנים בעצים השונים ובכך לבנות עץ שמתאים יותר לחיפוש של צירוף מרחבי מלחיפוש תחום.
בניית עץ שתול נעשית בצורה הבאה:
שלב שתילה - בשלב זה מועתקים k הרמות הגבוהות מהעץ R שנתון לעץ השתול שבונים (k הוא פרמטר שקובע את כמות הרמות). הערכים ברמה התחתונה של עץ זה מכונים חריצים, והמצביעים שמאוחסנים בהם הם לתתי עצים ריקים.
שלב גדילה - בשלב זה מוכנסים לתוך תת-העץ השתול כל העצמים בקבוצה שלא היה לא עץ. החריצים שנבחרים הם אלו שבהם הגדלת שטח המלבן החוסם תהיה הקטנה ביותר (במהלך שלב זה המלבן החוסם אינו בהכרח מינימלי). מאחר שהמלבנים בחריצים מבוססים על מלבנים חוסמים מינימליים מהקבוצה הראשונה, כשלעצם אין חפיפה עם לפחות אחד מערכי החריצים הוא מסונן.
שלב ניקוי - בשלב זה מתאימים את המלבנים החוסמים בצמתים של k הרמות בעץ השתול כך שיהפכו להיות מלבנים חוסמים מינימליים של הערכים שמתחתיהם. כמו כן מוחקים מהעץ השתול חריצים שנשארו עם מצביעים לתתי עצים ריקים.
בנוסף, הוצע שימוש בטכניקה לייעול הגישות לזיכרון החיצוני על ידי השהייה של בניית תתי העצים שמוצבעים מהחריצים עד לסיום המעבר על כל העצמים שמכניסים לעץ. במהלך הבנייה ערכים ייצברו במבני עזר זמניים.