עץ R
וריאציות > מידע מרחבי-זמני

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