עץ R

דוגמה לעץ R דו־ממדי שנבנה על בסיס המלבנים R8-R19, מבוסס על דוגמה מתוך המאמר המקורי על עצי R של אנטונין גוטמן

במדעי המחשב, עץ R הוא מבנה נתונים בצורת עץ שנועד לשמש לגישה למידע מרחבי, כלומר לנתונים עם אופי רב ממדי. נתונים אלו יכולים להיות קואורדינטות גאוגרפיות, מלבנים וצורות גאומטריות נוספות. עץ R הוצע לראשונה על ידי אנטונין גוטמן בשנת 1984,^[1] ומאז נעשה בו שימוש תאורטי ומעשי נרחב.^[2] האות R בשם של מבנה הנתונים היא קיצור למילה מלבן באנגלית - Rectangle.

סקירה

מבנה הנתונים של עץ R התבסס על עץ +B, והוא תוכנן כך שחיפוש של מידע מרחבי באמצעותו יצריך מעט גישות לצמתים ויתבצע בצורה מהירה. עץ R הוא עץ חיפוש מאוזן, שבו כל צומתי העלים של העץ הם באותו גובה, והעלים מכילים רשומות אינדקס ומצביעים לערכים בבסיס נתונים.

לכל הצמתים בעץ מוגדר סף מקסימום של ערכים שניתן לאחסן בהם, שמסומן כפרמטר ${\displaystyle M}$. כמות הערכים שניתנים לאחסון בצומת היא למעשה כמות הבנים שיכולים להסתעף ממנו והיא מכונה גם רמת הסתעפות (branching factor). האחסון הקבוע של עץ R הוא לרוב בזיכרון חיצוני למחשב, כי האינדקס נוטה להיות גדול מדי לאחסון בחוצץ בזיכרון הפנימי (שהקיבולת שלו קטנה יחסית). לכן נוח להגדיר גודל של צומת בעץ כך שיהיה זהה בקירוב לגודל של דף, ובכך בכל קריאה מהזיכרון החיצוני לפנימי יישלף צומת אחד. פרמטר המקסימום ${\displaystyle M}$ נקבע בפועל כך שניתן יהיה למלא דף בזיכרון בצורה מלאה ככל האפשר, וחישוב נתון זה מבוסס בעיקרו על גודל השדות ברשומת אינדקס וצורת הדחיסה שלהם בצומתי העץ, גודל מצביע (מושפע מגודל כתובת בזיכרון), וגודל הדף.

בנוסף מוגדר סף מינימום של ערכים שיכול להיות בצומת כפרמטר ${\displaystyle m}$ שמקיים את התנאי ${\displaystyle m\leq M/2}$. הגדרת סף מינימום זה מאפשרת לאכוף תפוסה מסוימת של ערכים בצמתים והיא משפיעה על האיזון של העץ. מצד אחד, אכיפה של תפוסה גבוהה מקטינה את כמות הצמתים ומשפיעה על גובה העץ להיות קטן, דבר שיוביל להקטנת כמות הקריאות של צמתים לזיכרון ולייעול הביצועים של חיפוש נתונים. מצד שני, אכיפה של תפוסה גבוהה מגדילה את כמות הצעדים הממוצעת שמבוצעת בכל פעולת הכנסה ומחיקה בעץ (כי נדרש לבצע פיצול צמתים ומחיקה שלהם בתדירות גבוהה יותר), ובכך מייקרת את עלות הביצועים שלהם.

בכל צומת שאינו השורש יש בין ${\displaystyle m}$ ל- ${\displaystyle M}$ ערכים. עבור עץ  R שמכיל ${\displaystyle N}$ רשומות אינדקס, מתקיים שגובה העץ הוא לכל היותר ${\displaystyle |log_{m}N|-1}$.‏^[3]

הרעיון העיקרי בעץ R הוא לקבץ עצמים שסמוכים זה לזה במרחב n-ממדי, ולייצג אותם ברמה גבוהה יותר בעץ על ידי המלבן ה-n ממדי הקטן ביותר שמקיף אותם ומקביל לצירים. מלבן זה מכונה גם מלבן חוסם מינימלי (Minimum Bounding Rectangle, MBR). מידע יאוחסן בעץ בצורה הבאה:

• ערך שמאוחסן בצומת עלה הוא זוג סדור שיכיל שני נתונים - עצם שמייצג נקודה או מלבן חוסם מינימלי במרחב n-ממדי, ומזהה ייחודי לאותו עצם בבסיס הנתונים.
• ערך שמאוחסן בצומת פנימי שאינו עלה הוא זוג סדור שיכיל שני נתונים - מלבן במרחב n-ממדי שמכסה את המלבנים של הערכים בצומתי הבנים שלו, ומצביע לצומת בן שלו בעץ.

מלבנים יכולים לחפוף בשטח שלהם זה לזה (כלומר יש חיתוך גאומטרי ביניהם), זאת בניגוד למבני נתונים כמו עץ +B או עץ kd שם אין חפיפות בין ערכים שמייצגים תחום של נתונים שמאוחסנים בצמתים.

פעולות

הכנסה

כדי להכניס ערך לעץ R, מבוצע מעבר על צמתים בעץ החל מצומת השורש. בכל שלב נבחנים המלבנים בצומת, ועל ידי היוריסטיקה מסוימת נבחר מלבן מסוים שמייצג תת-עץ כמועמד מתאים להכנסת הערך תחתיו. ייתכן שיהיו כמה מלבנים שיענו לקריטריון של ההיוריסטיקה ואלגוריתם ההכנסה יצטרך להכריע ביניהם. לאחר בחירת צומת מתאים האלגוריתם ממשיך לבצע מעבר בצורה רקורסיבית בתוך צומתי הבנים שלו עד להגעה לצומת עלה מתאים. אם צומת העלה מלא (יש בו כבר ${\displaystyle M}$ ערכים, ובשל כך מתרחשת גלישה - overflow), צריך לפצל אותו לפני שההכנסה תתבצע. כאן מבוצע שימוש בהיוריסטיקה נוספת לפיצול הערכים לשתי קבוצות מתאימות. בכל מקרה, לאחר הכנסה לצומת עלה, בודקים אם צריך לעדכן את הערך של המלבן בצומת האב, וכך הלאה בצורה רקורסיבית.

בדומה לעץ +B, גם כאן לאחר פיצול צומת עלה ההכנסה מפעפעת למעלה, כך שלאחר הפיצול מוכנס ערך חדש לצומת האב של העלה. לאחר מכן אם נדרש גם צומת האב מפוצל, וכך האלגוריתם ממשיך לפי הצורך בצורה רקורסיבית עד הגעה לצומת השורש. אם גם צומת השורש מלא ונדרש לפצל אותו, נוצר שורש חדש והגובה של העץ גדל בהתאמה.^[4]

בחירת תת-עץ להכנסה

בכל רמה בעץ, האלגוריתם צריך לבחור את תת-העץ שאליו יוכנס הערך - כלומר לבחור מלבן מתאים. כשהערך שרוצים להכניס מוכל כולו בתוך אחד המלבנים, הוא נבחר מיידית. אם יש כמה מלבנים שמכילים את הערך, הכרעה ביניהם נעשית בצורה אקראית. כשהערך שרוצים להכניס חופף חלקית לכמה מלבנים או שאינו מוכל כלל באף אחד מהם, לבחירת המלבן המתאים יש השפעה על הביצועים של העץ. הבחירה תלויה בקריטריונים של ההיוריסטיקה.

בעץ R קלאסי ההיוריסטיקה היא בחירת המלבן שמצריך הרחבה מינימלית של השטח שלו כדי להכניס בתוכו את הערך הנוסף, ובמקרה של שוויון ההכרעה היא על ידי בחירת המלבן שמייצג תת-עץ עם שטח קטן יותר. קיימות וריאציות משופרות של עץ R בהן יש היוריסטיקות אחרות. בעץ *R למשל נעשה שימוש בהיוריסטיקה משולבת: ברמת העלים נעשה ניסיון למזער את השטחים החופפים בין המלבנים (ובמקרה של שוויון ההכרעה היא על ידי שימוש בהיוריסטיקה של עץ R קלאסי), ואילו ברמות של צמתים פנימיים יותר בעץ נעשה ישירות שימוש בהיוריסטיקה של עץ R קלאסי.^[5]

פיצול צומת מלא

המטרה היא לצמצם את השטח המשותף ששני המלבנים בצמתים החדשים יכסו. מספר האפשרויות לחלוקה של ערכים מצומת אחד מלא לשני צמתים חדשים הוא אקספוננציאלי למספר הערכים שיש בצומת (סיבוכיות זמן ריצה של אלגוריתם נאיבי שממצה את כל האפשרויות יכולה להגיע ל- ${\displaystyle 2^{M-1}}$), ולכן צריך להשתמש בהיוריסטיקה כדי למצוא חלוקה מיטבית ככל שאפשר. גוטמן הציע שתי היוריסטיקות לפיצול צומת בעץ R קלאסי: פיצול ריבועי (quadratic split), ופיצול ליניארי (linear split).^[6] בשתי שיטות אלו מוצאים בהתחלה גרעין מתאים לכל אחת משתי קבוצות הערכים, ולאחר מכן מחלקים את שאר הערכים בין שתי הקבוצות שנוצרו בהתבסס על קריטריונים מסוימים.

• פיצול ריבועי (עם סיבוכיות זמן ריצה ריבועית):
  • האלגוריתם מחפש בהתחלה זוג מלבנים שהם הזוג הגרוע ביותר שאפשר לשבץ ביחד. זוג מוגדר כגרוע ביותר לשיבוץ ביחד אם לאחר הפחתת שטח זוג המלבנים משטח המלבן החוסם המינימלי שלהם מתקבל השטח הריק הגדול ביותר שלא מנוצל לעומת מלבנים חוסמים מינימליים אחרים. האלגוריתם משבץ את שני המלבנים שנבחרו כגרעינים לשתי קבוצות נפרדות בהתאמה. בניסוח פורמלי יותר, בהינתן צומת שמכיל את קבוצת המלבנים ${\displaystyle R}$, יש למצוא את זוג המלבנים ${\displaystyle a,b\in R}$ עם המלבן החוסם המינימלי ${\displaystyle r=MBR(a\cup b)}$ שממקסם את הערך ${\displaystyle area(r-area(a)-area(b))}$.
  • לאחר מכן האלגוריתם עובר בלולאה על המלבנים שנותרו, ומוסיף מלבנים לשתי הקבוצות. בכל פעם ייבחר להוספה מלבן שיש לו את 'ההעדפה החזקה ביותר' לאחת מהקבוצות בהקשרי הפרש בגידול של שטח. עבור כל מלבן מחושב הגידול בשטח של כל אחת הקבוצות לאחר הוספה שלו אליהן בהתאמה, ומסמנים את המלבן שההפרש בין גידולי השטח בשתי הקבוצות עבורו יהיה הגדול ביותר. בניסוח פורמלי יותר, בהינתן שני מלבנים חוסמים מינימליים ${\displaystyle r_{A},r_{B}}$ של שתי קבוצות ${\displaystyle A,B}$ וקבוצת מלבנים ${\displaystyle R}$ שטרם שובצו, יש למצוא את המלבן ${\displaystyle r\in R}$ שממקסם את הערך ${\displaystyle |area(MBR(r_{A}\cup r))-area(MBR(r_{B}\cup r))|}$.
  • הקבוצה שהאלגוריתם ייבחר להוסיף אליה את המלבן שנבחר היא זו שגידול השטח בה יהיה קטן יותר. במקרה של שוויון, ההכרעה תהיה הוספה לקבוצה שיש לה את השטח הכולל הקטן יותר; לאחר מכן ההכרעה על ידי בחירה בקבוצה עם מספר הערכים הקטן יותר, ולאחר מכן תהיה בחירה אקראית בין הקבוצות.
  • הלולאה מסתיימת אם התבצעה השמה של כל הערכים בשתי הקבוצות, או אם באחת הקבוצות יש כמות ערכים מינימלית מספקת. במקרה האחרון מוסיפים את הערכים שנשארו לקבוצה שכמות הערכים בה קטנה יותר.
• פיצול ליניארי (עם סיבוכיות זמן ריצה ליניארית):
  • האלגוריתם מחפש בהתחלה זוג של מלבנים שיש ביניהם את 'ההפרדה המנורמלת' הגדולה ביותר בין כל הממדים. בכל אחד מהממדים בוחרים זוג מלבנים שאחד מהם הוא המלבן שהצלע הגבוהה שלו שמקבילה לציר היא הנמוכה ביותר מבין כל הצלעות של המלבנים, והשני הוא המלבן שהצלע הנמוכה שלו שמקבילה לציר היא הגבוהה ביותר מבין כל הצלעות של המלבנים. בין שני מלבנים אלו יש את ההפרדה הגדולה ביותר באותו ממד. מנרמלים את ההפרדה באותו ממד על ידי כך שמחלקים את גודל ההפרדה בגודל הצלע של המלבן החוסם בצומת המקורי שמקביל לאותו ציר. האלגוריתם משבץ את שני המלבנים שנבחרו כגרעינים לשתי קבוצות נפרדות בהתאמה.
  • לאחר מכן האלגוריתם בוחר בצורה אקראית את הערכים שנותרו, ומחלק אותם בין שתי הקבוצות.
  • בחירת הקבוצה שאליה האלגוריתם יוסיף את הערך שנבחר תעשה באופן דומה להיוריסטיקה של פיצול ריבועי.

קיימות אסטרטגיות נוספות לפיצול צמתים מלאים - כמו שיטת הפיצול של גרין,^[7] היוריסטיקת הפיצול של *R שכוללת מחיקה של צמתים והכנסה מחדש שלהם,^[8] שיטת הפיצול של אנג וטן,^[9], ועוד.

עדכון

אם מבוצע עדכון לעצם שמוצבע ידי העלים והוא מוביל לשינוי המלבן החוסם המינימלי שלו, צריך למחוק את רשומת האינדקס של אותו עצם מתוך העץ (ביצוע פעולת מחיקה), ולהכניס את האינדקס המעודכן מחדש (ביצוע פעולת הכנסה).^[10] המשמעות היא שביצוע פעולות עדכון על נתונים בצורה תכופה בעץ R זה דבר יקר יחסית (דבר כזה יכול להידרש למשל עבור עצם שנע במהירות במרחב).

מחיקה

מחיקה של ערך מצומת בעץ R כרוכה תחילה במציאה של הצומת שמכיל את הערך שביקשו למחוק אותו (פעולת חיפוש), ואם נמצא צומת מתאים, מחיקה של הערך מאותו צומת. המחיקה עלולה לגרור צורך בעדכון של ערך מלבן בצומת האב.

במהלך המחיקה ייתכן שיהיה צורך למחוק ערך מצומת השורש. אם הערך היחיד שיש בצומת השורש הוא לא עלה, מתבצעת מחיקה של צומת השורש וסימון ערך הבן היחיד שלו כצומת שורש חדש. פעולה כזו מקטינה את הגובה של העץ.

בנוסף, על עץ R מוגדר תנאי לכמות מינימום של ערכים בצומת, לכן יש להתייחס גם אליו במהלך מחיקה. הטיפול בתנאי זה יתבצע בצורה שונה מזו שבה הוא מתבצע במבנה נתונים כמו עץ +B. בעץ +B, אם מגיעים למצב שבו רמת התפוסה של ערכים בצומת מסוים היא מתחת למינימום הנדרש (מצב של חמיקה - underflow), ניתן לפי הצורך להפעיל אלגוריתם מיזוג לשני צומתי אחים - מכיוון שהעץ מכיל אינדקס חד־ממדי שהערכים ממוינים לפיו. לעומת זאת, במידע רב ממדי, התכונה הזאת לא מתקיימת בהכרח.

לכן, במקום זאת, גוטמן הציע לבצע הכנסה מחדש של כל הערכים שנותרו בצומת שהיה בתת-תפוסה, ולמחוק אותו לחלוטין מהעץ. שיטה זו מאפשרת מימוש פשוט יותר של האלגוריתם כי היא עושה שימוש באלגוריתם של פעולת ההכנסה ונמנעת מאלגוריתם מיזוג ייעודי. כמו כן יש לה יתרון בעבודה עם בסיסי נתונים, מאחר שהדפים שדרושים להכנסה מחדש היו צריכים להיטען לחוצץ בזיכרון הפנימי כבר במהלך החיפוש של הרשומה שביקשו למחוק. כמו כן, מחיקה של נתונים פוגעת באיכות המלבנים החוסמים בעץ (על ידי יצירת שטחים ריקים וחפיפות בין מלבנים שכבר לא הכרחיות), והכנסה של נתונים מחדש אמורה לצמצם תופעות אלו.^[11]

שאילתות חיפוש מרחביות

חיפוש תחום

החיפוש הסטנדרטי בעץ R הוא חיפוש תחום (range searching) בו מחפשים עצמים שנמצאים בתחום מסוים במרחב שניתן כקלט. בעץ R קלט של חיפוש כזה הוא מלבן (שמכונה בשמות 'תחום', 'חלון', ו'מלבן שאילתה'), והתוצאה הרצויה היא קבוצה של העצמים שמוצבעים מעלי העץ וחופפים לאותו מלבן או מוכלים בו. מקרה פרטי לחיפוש כזה הוא כשהקלט מייצג נקודה.

חיפוש תחום נעשה בצורה דומה לחיפוש בעץ +B. כל צומת פנימי בעץ מכיל קבוצת ערכים שמייצגים מלבנים וקבוצת מצביעים לצומתי בנים, וכל עלה מכיל מצביעים לעצמים עצמם במרחב. החיפוש מתחיל בצומת השורש של העץ, ונעשית בדיקה לכל מלבן בקבוצת המלבנים בצומת האם יש חפיפה כלשהי בינו לבין קלט החיפוש. אם יש חפיפה כזו צריך להמשיך לבצע את החיפוש בצומת הבן בצורה דומה. החיפוש ממשיך בצורה רקורסיבית כך שהאלגוריתם יבקר בכל הצמתים שבהם הייתה חפיפה כלשהי לקלט החיפוש.^[12]

כשמגיעים לעלה, ייתכן מצב של חפיפה שגויה (false overlap) שבו המלבן החוסם המינימלי חופף לקלט החיפוש, אבל העצם החסום (שהוא לא בהכרח מלבן) לא חופף אליו. בשל כך יש לבדוק את החפיפה גם עבור העצם שמוצבע מהעלה. כשנמצאת חפיפה בין עצם באחד העלים לקלט החיפוש, אותו עצם מתווסף לקבוצת הערכים של התוצאה. ייתכן שבחיפוש מסוים לא יימצא אף עצם מתאים.

חיפוש השכן הקרוב ביותר

ישנן פעולות חיפוש נוספות שנפוצות בעץ R. למשל, חיפוש השכן הקרוב ביותר (nearest neighbor search), שמטרתו למצוא עצם שהוא השכן שקרוב ביותר במרחב ה-n ממדי לנקודה או למלבן מסוימים שניתנים כקלט.

אלגוריתם בצורה של הסתעף וחסום לביצוע חיפוש כזה בעץ R הוצע על ידי Roussopoulos‏, Kelley ו-Vincent בשנת 1995.^[13] לצורך האלגוריתם מוגדרות שתי מטריקות בין נקודה במרחב ה-n ממדי לנקודה אחרת במלבן n-ממדי באותו מרחב: מטריקת מרחק מינימלי, ומטריקת מרחק מינימקס. שיפור של האלגוריתם שמייעל את החישובים ומשתמש במטריקת מרחק מינימלי בלבד הוצג על ידי Cheung ו-Fu בשנת 1998.^[14]

צירוף מרחבי

פעולות חיפוש מסוג אחר הן פעולות שמצריכות סריקה חוזרת של העצמים שבמרחב. פעולה נפוצה כזו היא פעולת חיפוש של צירוף מרחבי (spatial join) עם פרדיקט של חיתוך שמוגדרת בצורה הבאה:^[15] עבור שני יחסים שמכילים קבוצות של עצמים במרחב, הצירוף המרחבי שלהם הוא קבוצת כל העצמים שחופפים בין הקבוצות. פעולה זו היא למעשה הרחבה של חיפוש תחום, כך שקלט החיפוש שהכיל מלבן יחיד יכיל קבוצה של מלבנים.

אלגוריתם נאיבי לצירוף מרחבי כזה הוא אלגוריתם שעושה שימוש בלולאות מקוננות והוא לא יעיל במיוחד בסיבוכיות זמן ריצה שלו עבור קבוצות גדולות של עצמים. אלגוריתמים שונים שמבוססים על עץ R ועל וריאציות שלו הוצעו כדי לייעל את הפעולה.

אחד האלגוריתמים הראשונים שמטרתו לבצע צירוף מרחבי בין שני יחסים שמיוצגים בשני עצי R עם גבהים שונים הוצע על ידי Brinkhoff,‏ Kriegel,‏ ו-Seeger ב-1993^[16]. אלגוריתם זה מכונה לפעמים אלגוריתם RJ ‏(R-tree Join) או אלגוריתם התאמת עץ, ופועל בצורה של חיפוש לעומק:

• תחילה נעשה ניסיון לצמצם את מרחב החיפוש על ידי חישוב השטח החופף בין המלבנים שמייצגים את השורשים של העצים ופסילת צומתי הבנים שלא יכולים לחפוף לשטח זה.
• לאחר מכן נבנית רשימה ממויינת של מלבני הבנים שנשארו בהתבסס על סדר עולה של ערכי קואורדינטה באחת הקודקודים - למשל על פי ערך ה-x בקודקוד השמאלי התחתון שלהם. על רשימה זו מתבצע מעבר באלגוריתם סריקת מישור (plane sweep algorithm) תוך עצירה בנקודת ה-x הממויינת של כל מלבן, ומציאת זוגות מתאימים של מלבנים משני העצים שחופפים זה לזה.
• בסריקה נעשה שימוש במנגנון שמטרתו להצמיד את הזוגות שאליהם שייך המלבן שיש לו את הכמות הגדולה ביותר של חפיפות עם מלבנים אחרים. בכך מנסים לאפשר למלבן שמשתתף ביותר פעולות יחסית למלבנים האחרים 'להינעץ' בזיכרון הפנימי, והדבר מייעל את הביצועים של האלגוריתם.
• עבור כל זוג מלבנים חופפים האלגוריתם מופעל בצורה רקורסיבית על שני תתי העצים שהם מייצגים, וכך הלאה עד שאחד מתתי העצים הוא עלה. במצב כזה עוברים על כל המלבנים שמוצבעים באותו עלה, ומשתמשים בהם כקלטים לפעולות חיפוש של מלבן בתת-העץ השני. עצמים שנמצאה ביניהם חפיפה מתווספים לקבוצת הערכים של תוצאת הצירוף המרחבי.

למצבים בהם רק אחד מהיחסים מיוצג בעץ R, הוצע אלגוריתם לבניית עץ מתאים ליחס השני על ידי Lo ו-Ravishankar בשנת 1994.^[17] מבנה הנתונים הנוסף שמוגדר עבור היחס השני הוא עץ שתול (seeded tree) והוא מתבסס על ערכים מהעץ R שכבר נתון. הרעיון בבנייה כזו הוא לצמצם את כמות החפיפות שיימצאו בין זוגות מלבנים בעצים השונים ובכך לבנות עץ שמתאים יותר לחיפוש של צירוף מרחבי מלחיפוש תחום.

• בניית עץ שתול נעשית בצורה הבאה:
  • שלב שתילה - בשלב זה מועתקים k הרמות הגבוהות מהעץ R שנתון לעץ השתול שבונים (k הוא פרמטר שקובע את כמות הרמות). הערכים ברמה התחתונה של עץ זה מכונים חריצים, והמצביעים שמאוחסנים בהם הם לתתי עצים ריקים.
  • שלב גדילה - בשלב זה מוכנסים לתוך תת-העץ השתול כל העצמים בקבוצה שלא היה לא עץ. החריצים שנבחרים הם אלו שבהם הגדלת שטח המלבן החוסם תהיה הקטנה ביותר (במהלך שלב זה המלבן החוסם אינו בהכרח מינימלי). מאחר שהמלבנים בחריצים מבוססים על מלבנים חוסמים מינימליים מהקבוצה הראשונה, כשלעצם אין חפיפה עם לפחות אחד מערכי החריצים הוא מסונן.
  • שלב ניקוי - בשלב זה מתאימים את המלבנים החוסמים בצמתים של k הרמות בעץ השתול כך שיהפכו להיות מלבנים חוסמים מינימליים של הערכים שמתחתיהם. כמו כן מוחקים מהעץ השתול חריצים שנשארו עם מצביעים לתתי עצים ריקים.
• בנוסף, הוצע שימוש בטכניקה לייעול הגישות לזיכרון החיצוני על ידי השהייה של בניית תתי העצים שמוצבעים מהחריצים עד לסיום המעבר על כל העצמים שמכניסים לעץ. במהלך הבנייה ערכים ייצברו במבני עזר זמניים.

וריאציות

רוב המחקר בעצי R (נכון ל-2017) נעשה בתחומים הבאים:

• שיפור בנייה של עץ בטעינה באצווה (בניית עץ לאינדקס מקבוצה גדולה נתונה של ערכים בבת אחת). בטעינה כזו רמת העלים נבנית לרוב מראש על פי קריטריונים מתאימים, ומהם העץ נבנה כלפי מעלה בצורה רקורסיבית.
• שיפורים להכנסת נתונים ומחיקת נתונים שאינם ידועים מראש בצורה דינמית.
• מנגנונים לייעול שימוש בעץ במספר מערכות אחסון בארכיטקטורה מקבילית, ומנגנונים שמאפשרים בקרת בו זמניות בטיפול במידע.
• הרחבות לתמיכה במידע מרחבי-זמני (מרחבי-טמפורלי), שבנוסף על היותו מבוסס על נתונים במרחב הוא מבוסס גם על נתוני זמן.
• הרחבות לתמיכה במידע מרחבי-טקסטואלי, שבו הנתונים במרחב מעוטרים במילות מפתח מתאימות ובטקסט תיאורי.
• שיפורים לתמיכה יעילה יותר במידע עם כמות ממדים מסדר גבוה (עשרות או מאות), למשל מולטימדיה שמכילה נתוני קול, קובצי תמונות, וידאו וכדומה.

טעינה באצווה

• עץ R ארוז (מכונה גם Nearest-X): וריאציה שהוצעה על ידי Roussopoulos ו-Leifker בשנת 1985.^[18] נועדה לשימוש בסיסי נתונים שבהם יש שינויים מועטים במידע לאחר ההכנסה שלו לבסיס נתונים - למשל, נתונים בסיסיים של מפות גאוגרפיות. בכל צומת התפוסה צריכה להיות מלאה ככל האפשר. הטעינה מתבצעת על ידי אלגוריתם אריזה (Packing) שנעזר במיון של הערכים על פי קריטריון מרחבי כלשהו, למשל על ידי סדר עולה של קואורדינטה בציר x, והשכנים הקרובים ביותר על פי הקריטריון (Nearest-X) משובצים בסמיכות זה לזה בעלים.
• עץ STR R ‏(Sort-Tile-Recursive R-tree): וריאציה שהוצעה על ידי Leutenegger,‏ Edgington, ו-Lopez ב-1997.^[19] זוהי וריאציה של עץ R ארוז לפי קריטריון Nearest-X. הרעיון הוא למיין קבוצה של מלבנים n-ממדיים לפי ממד מסוים (למשל ציר x) ולרצף את מרחב הנתונים על ידי אריחים שכל אחד מהם הוא קבוצה של מלבנים (תוך הגדרת פרמטר מתאים לגודל של אריח). לאחר מכן יש לעבור על כל אריח בצורה רקורסיבית, למיין את המלבנים שבתוכו לפי ממד פנימי y, לבצע ריצוף פנימי של אותו אריח, וכך הלאה בצורה רקורסיבית עד לסיום המעבר על n הממדים.
• עץ R חוצץ: וריאציה שהוצעה על ידי Arge,‏ Hinrichsy‏, Vahrenholdz ו-Vitterx בשנת 2002.^[20] וריאציה זו מבוססת על טכניקת עץ חוצץ של ביצוע פעולות בצורה 'עצלה'. המטרה שלה היא לאפשר טעינה באצווה גם כשלא ניתן לבנות את כל העץ מראש, וכן לאפשר טעינה שמערבת פעולות שונות של הכנסה, עדכון ומחיקה. הרעיון הוא להצמיד לצמתים ברמות נבחרות של העץ מבנה עזר של חוצץ. הרמות הנבחרות וגודל החוצץ שמוצמד לצמתים תלויים בגודל חוצץ בזיכרון החיצוני, בגודל הכולל של הזיכרון הפנימי, ובגודל הדרוש לייצוג מלבן. ערכים מאוחסנים בצורה זמנית בחוצצים של צמתים ברמות המתאימות, עד שחוצץ מגיע לרמת תפוסה מתאימה שנקבעה מראש. במצב זה חלק מהערכים בחוצץ מועברים הלאה להמשך ביצוע ברמות נמוכות יותר בעץ, תוך השהיה ברמת החוצצים הבאה, וכך הלאה. כמו כן, בפעולת מחיקה בעץ כזה מבוצע מיזוג בין צמתים בתת-תפוסה ולא מבוצעת הכנסה מחדש של ערכים לעץ.
• עץ Priority R (מכונה גם עץ PR): וריאציה שהוצעה על ידי Arge,‏ De Berg,‏ Haverkort, ו-Yi בשנת 2004.^[21] וריאציה זו היא הכלאה בין עץ R לבין עץ kd. במהלך בניית העץ הרקורסיבית נבנות 4 קבוצות של ערכי עדיפויות שמכילות כל אחת מלבנים עם ערכי קיצון של מינימום ומקסימום בציר ה-x ובציר ה-y בהתאמה. לאחר מכן מתבצעת חלוקה של הערכים שנשארו (אם יש כאלו) לשתי קבוצות נוספות תוך התייחסות אליה כאל סבב חלוקה בבנייה של עץ kd עם 4 ממדים, ובכל קבוצה כזו נבנות מחדש תתי קבוצות עם ערכי עדיפויות ומתבצעים סבבי חלוקה נוספים באופן רקורסיבי. מכלל קבוצות ערכי העדיפויות שנוצרו באלגוריתם נבנית רמת העלים של עץ PR. לווריאציה זו יש סיבוכיות זמן ריצה אופטימלית במקרה הגרוע לעומת עץ R קלאסי, כך שהיא מתאימה יותר מווריאציות אחרות למידע שמכיל מלבנים שהיחסים בין הגדלים שלהם קיצוניים.

וריאציות דינמיות

הקושי בבניית עץ R הוא שמצד אחד צריך לבנות עץ שהוא מאוזן, ומצד שני צריך שמלבנים לא יחפפו יותר מדי, כך שבמהלך חיפוש נתונים לא יהיה צורך לבקר בתתי עצים רבים, וכן שמלבנים לא יכסו יותר מדי אזורים ריקים (אזורים שלא מכוסים על ידי שטח מלבני בנים) כי אז אזורי החפיפה גדלים. וריאציות שונות של עץ R הוצעו כדי לשפר את פעולות ההכנסה, העדכון והמחיקה של הנתונים.

• עץ +R: וריאציה שהוצעה על ידי Sellis,‏ Roussopoulos, ו-Faloutsos ב-1987.^[22] המטרה של וריאציה זו היא להימנע מחפיפות של מלבנים בין צמתים פנימיים באותה רמה על ידי הכנסה של ערך למספר עלים אם צריך, וחיתוך מלבנים (clipping) כך שלא תהיה ביניהם חפיפה.
• עץ *R: וריאציה שהוצעה על ידי Beckmann,‏ Kriegel,‏ Schneider, ו-Seeger ב-1990.^[23] בווריאציה זו יש שימוש במספר היוריסטיקות נוספות באלגוריתם ההכנסה (שמשמש גם הכנסה מחדש של נתונים) מעבר להיוריסטיקה הקלאסית בעץ R של מציאת השטח קטן ככל האפשר שמכוסה על ידי המלבנים.
• עץ R הילברט: וריאציה שהוצעה על ידי Kamel ו-Faloutsos בשנת 1994.^[24] וריאציה זו היא הרחבה של עץ +B שבה עצמים גאומטריים מאופיינים על ידי ערך הילברט של המרכז הגאומטרי של המלבן החוסם המינימלי שלהם, ונעשה שימוש בעקומת הילברט (סוג של עקומת מילוי מרחב) כדי להגדיר סדר ליניארי על המלבנים. בשל כך, אלגוריתם ההכנסה של נתונים בעץ זה שונה משמעותית מהאלגוריתם הקלאסי, והוא לא מחייב בהכרח פיצול של צמתים.
• עץ RUM: וריאציה שהוצעה על ידי Xiong ו-Aref בשנת 2005.^[25] המטרה שלה היא לייעל טיפול בנתונים שמתעדכנים בתדירות גבוהה. לכל צומת עלה נוספת חותמת - מזהה ייחודי שמחולק לעלים בעץ ומקודם בצורה עולה סדרתית. בזיכרון הפנימי מתוחזק מבנה עזר שמכיל מידע על מזהי העצמים בבסיס הנתונים, מזהה ייחודי עדכני של עלה שמצביע אליהם, וכמות מקסימלית של מופעים של אותו עצם שהתיישנו ועדיין קיימים בעץ. הגישה למבנה זה מבוססת על טכניקה של תזכור (memoization) ובמהלך פעולת עדכון היא נמנעת מגישה לזיכרון חיצוני לצורך מחיקה של נתוני אינדקס ישנים מהעץ. בכך עלות פעולת עדכון היא כעלות של פעולת הכנסה בלבד. קבוצות של נתונים ישנים נמחקות מעץ RUM בבת אחת בתהליך של איסוף זבל לאחר שהתבצעה כמות מסוימת של עדכונים בעץ. קיימים מנגנונים נוספים להתאוששות מתקלות, בקרת בו זמניות, והתמודדות עם פעולות על נתונים שאינם קיימים בעץ.

מקביליות

ניתן לאחסן עץ R בארכיטקטורת חומרה שמורכבת מכמה אמצעי זיכרון חיצוניים, למשל דיסקים קשיחים. יעילות של שיטת אחסון כזו נבחנת בהקטנת זמן התגובה של פעולות בעץ.

• עץ MX R ‏(Multiplexed R-tree): וריאציה שהוצעה על ידי Kamel ו-Faloutsos בשנת 1992.^[26] וריאציה זו מתייחסת לשימוש במעבד אחד ובקבוצה של דיסקים קשיחים. המטרה שלה היא לבזר את הגישות לצמתים בין אמצעי האחסון בהתפלגות אחידה ככל האפשר. לכל צומת חדש שנוצר בעץ נבחר הדיסק המתאים לאחסון שלו, תוך שימוש במדד שמכונה 'אינדקס קרבה'. מדד זה מוגדר בין מלבן לקבוצת מלבנים על ידי היוריסטיקה שמעריכה את ההסתברות שיהיה צורך לגשת אליהם באותה שאילתת חיפוש, כשהיא מבוססת בחישובים שלה על מטריקה של מרחק בין המלבנים בכל ממד. האלגוריתם של ההכנסה בוחר עבור צומת חדש את הדיסק שיש לו את אינדקס הקרבה הנמוך ביותר אליו (במקרה של שוויון ההכרעה היא על ידי בחירת הדיסק עם כמות הצמתים הנמוכה יותר). בכך ניתן למקבל את הגישה למלבנים שיש ביניהם קרבה גבוהה.

מידע מרחבי-זמני

הרחבות שונות עוסקות במצבים שבהם יש עצמים רבים שנעים במרחב ומדווחים את נקודת המיקום העדכנית שלהם למשך זמן מסוים בתדירות גבוהה. שאילתות חיפוש נפוצות שמבוצעות על עצמים כאלו הן ביצוע חיפוש תחום עם קלט שנע במרחב בקטע מסוים של הזמן, ובפרט שאילתת חתך זמן (מיקום של עצמים במרחב בנקודת זמן מסוימת).

• עץ STR ‏(Spatiotemporal R-tree): וריאציה שהוצעה על ידי Pfoser, ‏Jensen, ‏ו-Theodoridis והוצגה בשנת 2000.^[27] המטרה שלה היא לאפשר לבצע בצורה נוחה שאילתות חיפוש שונות על מסלולים של עצמים שהיו בתנועה. מסלול של עצם מוגדר כשרשרת פוליגונלית שהיא אוסף קווים ישרים שמחברים בין נקודות המיקום השונות שלו לפי סדר זמן הדיווח שלהם, ומחושבים על ידי אינטרפולציה ליניארית. לכל קו במסלול מגדירים גם את כיוון התנועה שלו במרחב. עלה בעץ STR מייצג קו כזה, כך שבנוסף על הנתונים הקלאסיים הוא מכיל מזהה מסלול ושדה שמייצג את כיוון הקו. פעולת ההכנסה בעץ זה מעדנת את התנאי של תפוסת מינימום של ערכים בצומת, ובמקום זאת מגדירה בחירת תת-עץ ופיצול צומת מלא בצורה שמנסה לשמר קווים ששייכים לאותו מסלול סמוכים זה לזה ככל שניתן. לצורך כך מוגדר גם פרמטר נוסף ${\displaystyle p}$ ‏(preservation), שמגדיר בכמה רמות של צמתים יש לנסות לאכוף שימור מסלול על פני ההיוריסטיקות של עץ R קלאסי.
• עץ TPR ‏(Time Parametrized R-tree): וריאציה של עץ *R שהוצעה על ידי Saltenis, ‏Jensen, ‏Leuteneggerz, ו-Lopez בשנת 2000.^[28] המטרה שלה היא לאפשר לבצע שאילתות חיפוש על מיקום של עצמים בעודם נעים במרחב, וכן לאפשר להעריך את המיקום של העצמים בעתיד. בעץ TPR ערך בצומת עלה מייצג נקודת מיקום במרחב, והקואורדינטות של המלבן החוסם בעלה (שמכונה במקור 'מלבן חוסם משמר') הן פונקציות על המיקום והמהירות של העצמים בתוכו שתלויות בפרמטר של הזמן. המלבן יכול לנוע עם העצמים על פני המרחב, וכשמתרחש עדכון במלבן של עלה הוא מפעפע למלבנים החוסמים של צומתי האב. בפעולת ההכנסה ההיוריסטיקות מחושבות בעזרת אינטגרל על פני ציר הזמן, ובפיצול צומת מלא חלוקת העצמים מושפעת גם מוקטור המהירות שלהם.
• עץ MV3R‏ (Multi-version 3D R tree): וריאציה שהוצעה על ידי Tao ו-Papadias בשנת 2001.^[29] היא נועדה לנתוני מיקום מהעבר, ונעשה בה שימוש בעץ MVR^[30] שמטרתו לייעל שאילתות חתך זמן וחיפוש נתוני מיקום בקטעי זמן קצרים, ובמבנה עזר של עץ R רגיל עם שלושה ממדים שנועד עבור חיפוש בקטעי זמן ארוכים. עץ MVR מכיל אוסף של מבני נתונים מבוססי עץ R שמטרת כל אחד מהם לייצג נתוני מיקום בחתך מסוים של ציר הזמן. עבור כל ערך נשמר בעץ גם זמן ההכנסה שלו והזמן בו הפסיק להתקיים (אם יש כזה). בתנאים מסוימים יכולים להיווצר כמה עותקים לאותם נתוני מיקום, עם שוני בערכי הזמנים שנשמרים עבורם. עדכון של ערכים שמוצבעים מעלי עץ MVR מחלחל בצורה ישירה לתוך מבנה העזר של העץ R, בו יש נתוני מיקום דו־ממדיים והזמן הוא ממד נוסף ללא התייחסות מיוחדת. כשגודל קטע הזמן בקלט החיפוש חוצה סף מסוים, החיפוש מבוצע במבנה העזר.
• עץ MON‏: וריאציה שהוצעה על ידי De Almeida ו-Güting והוצגה בשנת 2005.^[31] היא נועדה לנתוני מיקום מהעבר, והמטרה שלה היא לייעל שאילתות על עצמים שהתנועה שלהם מתאפשרת רק ברשת של נתיבים ספציפיים שמוגדרים מראש (למשל, רשת של כבישים או מסילות רכבות). בעץ MON רשת ממודלת לרוב כקבוצה של נתיבים שהם שרשראות פוליגנליות (קווים ישרים שמחוברים ביניהם) וכקבוצה של צומתי מפגש בין הנתיבים.^[32] נקודת מיקום של עצם בנתיב מסוים מתוארת באופן יחסי לקצוות שלו, ותנועה של עצם על פני נתיב בקטע זמן מסוים מתוארת על ידי נקודות מיקום של העצם בתחילת קטע הזמן ובסיומו. רשת הנתיבים מיוצגת על ידי עץ R דו־ממדי, וכל נתיב בעלים של עץ זה מצביע לעץ R דו־ממדי נוסף שמאחסן מידע על תנועה של עצמים באותו נתיב. על מנת לייעל את הפעולות, נעשה שימוש במבנה עזר של טבלת גיבוב שממפה בין מזהי נתיבים לעצי R שמוצבעים מהם.

מידע מרחבי-טקסטואלי

הרחבות שונות עוסקות בנקודות במרחב שלכל אחת מהן מוצמד מסמך טקסט עם מלל תיאורי:

• עץ CDIR‏: וריאציה שהוצעה על ידי Cong, ‏Jensen ו-Wu בשנת 2009.^[33][34] המטרה של וריאציה זו היא לאפשר חיפוש של k-השכנים הקרובים ביותר במרחב לנקודה מסוימת שיש לטקסט שבמסמך שלהן התאמה כלשהי גם לקלט טקסטואלי של מילות מפתח. הווריאציה מבוססת על עץ IR, שבו לכל צומת פנימי בעץ R מתווסף מצביע למבנה נתונים מסוג אינדקס מהופך (Inverted Index) שמייצג את המידע הטקטסטואלי של כלל הבנים באותו צומת. בווריאציית עץ CDIR יש שתי הרחבות בולטות: לכל מסמך טקסט מוצמדת תווית שמייצגת אותו, כך שעבור מסמכים של בנים עם תוויות שונות יהיו בצומת אב כמה קובצי אינדקס מהופכים; בנוסף, פעולת ההכנסה לצומת מתייחסת גם לשיקולים של מדדי דמיון בין מילים בטקסטים שמוצמדים לנקודות במרחב.

ממדים מסדר גבוה

הגדלת כמות הממדים בעץ R שמאחסן מידע מרחבי פוגעת ביעילות של השימוש באינדקס, ובמקרים מסוימים השימוש באינדקס עלול אפילו להיות גרוע יותר מסריקה סדרתית של הנתונים. תופעה כזו נצפתה גם בשיטות אחרות, והיא מכונה בצורה כללית גם קללת הממד.^[35][36] וריאציות שונות הוצעו בניסיון לזהות את הגורמים הספציפיים לתופעה בעץ R ולהימנע מהם.

• עץ X‏: וריאציה שהוצעה על ידי Berchtold‏, Keim ו-Kriegel בשנת 1996.^[37] בווריאציה זו נעשה שימוש באלגוריתם פיצול צמתים שהמטרה של ההיוריסטיקות שלו היא להימנע מחפיפות בין המלבנים ככל שאפשר. במצב שבו לא נמצאת חלוקה כזו שמקיימת גם את סף המינימום של ערכים בצמתים החדשים הפיצול יבוטל, ובמקום זאת ייווצר 'צומת על' שבו יש תפוסת יתר של ערכים מעבר לסף המקסימום. מחיקה של ערכים מצומת על יכולה להפוך אותו לצומת רגיל בחזרה.

קישורים חיצוניים

מדיה וקבצים בנושא עץ R בוויקישיתוף

• מימוש עץ R בשפות תכנות נפוצות:
  • C++ & C
  • Java
  • Common Lisp
  • Python
  • 2D R-tree implementation in Scala
  • JavaScript
  • JavaScript - including interactive demo

הערות שוליים

1. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984
2. Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis. R-Trees: Theory and Applications, Springer, 2006
3. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, p. 48
4. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 49-50
5. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90, 1990, pp. 325-326
6. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, p. 52
7. Diane Greene, An implementation and performance analysis of spatial data access methods, [1989] Proceedings. Fifth International Conference on Data Engineering, 1989, pp. 606–615
8. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90, 1990, p. 326
9. C. H Ang; T. C. Tan, New linear node splitting algorithm for R-trees. In Michel Scholl; Agnès Voisard. Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997, Lecture Notes in Computer Science, Vol. 1262,pp. 337–349
10. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, p. 51
11. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 50-51
12. Antonin Guttman, R-Trees: A Dynamic, Index Structure for Spatial Searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 48-49
13. Nick Roussopoulos, Stephen Kelley, Frédéric Vincent, Nearest Neighbor Queries, In ACM SIGMOD record, vol. 24, no. 2, pp. 71-79. ACM, June 1995
14. King Lum Cheung, and Ada Wai-Chee Fu. Enhanced nearest neighbour search on the R-tree, In ACM SIGMOD Record, vol. 27, no. 3, Sep. 1998, pp. 16-21
15. הוגדרה על ידי: Orenstein, Jack A., Spatial query processing in an object-oriented database system, In ACM Sigmod Record, vol. 15, no. 2, p. 329. ACM, 1986. Harvard
16. Brinkhoff, T., Kriegel, H.P. and Seeger, B., Efficient processing of spatial joins using R-trees, SIGMOD '93 Proceedings of the 1993 ACM SIGMOD international conference on Management of data (Vol. 22, No. 2), ACM, Vancouver, June 1993,, pp. 237-246
17. Lo, Ming-Ling, and Chinya V. Ravishankar., Spatial joins using seeded trees. In ACM SIGMOD Record, vol. 23, no. 2, pp. 209-220. ACM, 1994.
18. N. Roussopoulos and D. Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the ACM SIGMOD Conference, Austin, TX, May 1985, pp. 17-31
19. Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A., STR: A Simple and Efficient Algorithm for R-Tree Packing, ICASE Report No. 97-14, 1997
20. Arge, Lars, Klaus H. Hinrichs, Jan Vahrenhold, and Jeffrey Scott Vitter, Efficient bulk operations on dynamic R-trees, Algorithmica (Vol. 33, no. 1), Harvard, May 2002, pp. 104-128.
21. L. Arge; M. de Berg; H. J. Haverkort; K. Yi, The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, SIGMOD, 2004
22. Timos Sellis, Nick Roussopoulos, and Christos Faloutsos, The R+-Tree: A dynamic index for multi-dimensional objects, Proceedings of 13th International Conference on Very Large Data Bases (VLDB), 1987, pp. 507-518
23. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90, 1990, pp. 322-331
24. Ibrahim Kamel and Christos Faloutsos, Hilbert R-tree: An improved R-tree using fractals, Proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, September 1994, pp. 500-509
25. Xiong, X. and Aref, W.G., R-trees with update memos, in: Computer Science Technical Reports, Paper 1634, Purdue University, October 2005
26. Kamel, I. and Faloutsos, C., Parallel R-trees, In Proceedings of the 1992 ACM SIGMOD International conference on Management of data (SIGMOD), Vancouver, (Vol. 21, No. 2), pp. 195-204, June 1992
27. Pfoser, Dieter, Christian S. Jensen, and Yannis Theodoridis. Novel approaches to the indexing of moving object trajectories. In Proceedings of the 26th International Conference on Very Large Databases (VLDB), Cairo, Egypt, pp. 395-406, September 2000.
28. Šaltenis, Simonas, Christian S. Jensen, Scott T. Leutenegger, and Mario A. Lopez. Indexing the positions of continuously moving objects. In Proc. of the ACM Intl. Conf. on Management of Data, SIGMOD (Vol. 29, no. 2), pp. 331-342, May 2000
29. Tao, Y., & Papadias, D, The MV3R-tree: A spatio-temporal access method for timestamp and interval queries, In Proceedings of Very Large Data Bases Conference (VLDB), Rome, pp. 431-440, September 2001,
30. עץ MVR הוא וריאציה של עץ R שמבוססת על הרעיון של וריאציית עץ MVB עבור עץ B: ‏Becker, B., Gschwind, S., Ohler, T., Seeger, B., & Widmayer, P. An asymptotically optimal multiversion B-tree. The VLDB Journal - The International Journal on Very Large Data Bases, Vol. 5 (No. 4), pp. 264-275, 1996
31. De Almeida, V. T., & Güting, R. H., Indexing the trajectories of moving objects in networks, pp. 1-27 (from GeoInformatica, Vol. 9 (No. 1), pp. 33-60), 2005.
32. ניתן למדל את הרשת גם כקבוצה של קודקודים וקשתות, אבל זה פחות יעיל מעשית: De Almeida, V. T., & Güting, R. H., Indexing the trajectories of moving objects in networks, p. 6 (from GeoInformatica, Vol. 9 (No. 1), p. 49), 2005
33. Cong, G., Jensen, C. S., & Wu, D. Efficient retrieval of the top-k most relevant spatial web objects, Proceedings of the VLDB Endowment, (Vol. 2, no. 1), 2009, pp. 337-348
34. וריאציה זו מבוססת על עץ IR של Cong et al. קיימת וריאציה נוספת בשם עץ IR שהוצעה בנפרד בשנת 2011 (Z. Li, K. C. K. Lee, B. Zheng, W.-C. Lee, D. L. Lee, and X. Wang. IR-tree: An efficient index for geographic document search, IEEE Transactions on Knowledge and Data Engineering, Vol. 23, no. 4, pp. 585–599, 2011). כדי להבדיל בין הווריאציות מזכירים את שמות המחברים, או שלפעמים מכנים את הווריאציה השנייה בשם עץ IRLi.
35. K-I. Lin, H. V. Jagadish and C. Faloutsos, The TV-Tree: An Index Structure for High-Dimensional Data, The VLDB Journal (Vol. 3, no. 4), pp. 519-520, 1994.
36. S. Berchtold, D.A. Keim and H.P. Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22nd VLDB Conference, Mumbai, India, pp. 29-31, 1996
37. S. Berchtold, D.A. Keim and H.P. Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22nd VLDB Conference, Mumbai, India, pp. 28-39, 1996