孟凡榮等所著《多版本TPR樹》。文中參考TR樹構(gòu)建了多版本TPR樹。文中稱多數(shù)算法參考TR樹，我并沒有看過TR樹的文獻(xiàn)，故具體算法尚不清楚。僅從文中所述來看TPR樹是一種全時(shí)態(tài)的索引。其中的每一條記錄都有一個(gè)起始時(shí)間和一個(gè)終止時(shí)間，并設(shè)置一個(gè)特定的終止時(shí)間代表“未來”，以表示這個(gè)記錄尚未終止。每當(dāng)一個(gè)記錄被終止的時(shí)候(比如刪除或者更新)，都將這個(gè)記錄的終止時(shí)間由“未來”改為一個(gè)固定的時(shí)間，然后把父節(jié)點(diǎn)的指針指向這個(gè)節(jié)點(diǎn)修改后的一個(gè)副本(如果是更新)或者把父節(jié)點(diǎn)的指針置空(如果是刪除)。這樣一來，如果根節(jié)點(diǎn)更新，就會產(chǎn)生一個(gè)新的根節(jié)點(diǎn)；如果中間節(jié)點(diǎn)更新，相當(dāng)于子樹產(chǎn)生了一個(gè)新的根節(jié)點(diǎn)。因此這一數(shù)據(jù)結(jié)構(gòu)稱為“多版本”。多個(gè)根節(jié)點(diǎn)可以用隊(duì)列或者哈希表管理。由于整個(gè)樹自始至終沒有真的進(jìn)行磁盤刪除操作，所以舊節(jié)點(diǎn)的指針仍然有效。那么，提出查詢的時(shí)候，先根據(jù)時(shí)間判斷應(yīng)該查詢哪個(gè)根節(jié)點(diǎn)，然后逐級向下判斷即可查到記錄過去的位置或者未來的位置。這個(gè)做法有明顯的缺陷，如果更新頻率很高，則索引會迅速增大。但是考慮到全時(shí)態(tài)數(shù)據(jù)庫的數(shù)據(jù)自身生長速度也極快，這個(gè)缺點(diǎn)或許可以容忍。另一個(gè)問題或許更為致命。文中稱當(dāng)一個(gè)MBR被刪除或更新時(shí)發(fā)生“版本分裂”，那么，在極端情況下，樹只有根節(jié)點(diǎn)，當(dāng)其中的一個(gè)記錄發(fā)生更新后，更新前的那個(gè)記錄將失去父節(jié)點(diǎn)。記錄發(fā)生更新時(shí)令其父節(jié)點(diǎn)版本分裂也不現(xiàn)實(shí)，因?yàn)檫@意味著每次版本分裂都會導(dǎo)致根節(jié)點(diǎn)版本分裂。雖然沒有證實(shí)，但是這個(gè)問題似乎有可能導(dǎo)致時(shí)間軸斷裂。這個(gè)問題具體如何解決可能要參考TR樹的算法。

金澤峰等所著《TPR樹性能優(yōu)化研究》。文中對TPR樹提出了兩點(diǎn)改進(jìn)。其一是節(jié)點(diǎn)分裂算法。TPR樹的節(jié)點(diǎn)分裂算法繼承了R*樹算法，根據(jù)周長選軸，根據(jù)面積分組。而此文作者經(jīng)試驗(yàn)后認(rèn)為，應(yīng)當(dāng)根據(jù)邊長選軸，根據(jù)周長分組。根據(jù)邊長選軸可以簡化計(jì)算而不會導(dǎo)致太差的性能差距，根據(jù)周長分組可以簡化計(jì)算、不會導(dǎo)致太嚴(yán)重的性能差距、容易產(chǎn)生更接近正方形的分組。另一個(gè)改進(jìn)是樹的調(diào)整策略。當(dāng)TPR樹發(fā)生更新時(shí)(插入前或者刪除后)，檢查相應(yīng)葉子節(jié)點(diǎn)中有沒有超過某個(gè)閾值的記錄。如果有，則重新插入。這個(gè)閾值采用動(dòng)態(tài)值，與整個(gè)索引空間在各軸上的投影長度線性相關(guān)。此文作者通過實(shí)驗(yàn)認(rèn)為，這樣修改后的TPR樹性能更好。

李東等所著《基于Quadtree和Hash表的移動(dòng)對象全時(shí)態(tài)索引》。文中提出了一種全時(shí)態(tài)索引，實(shí)際上已經(jīng)類似于提出了一種數(shù)據(jù)管理方式。這種索引方式對每個(gè)對象都提供一個(gè)標(biāo)識，使用哈希表將所有的移動(dòng)對象管理起來。將移動(dòng)對象的歷史軌跡劃為線段，串成一個(gè)線表。移動(dòng)對象的當(dāng)前位置則存入四叉樹索引中，同時(shí)四叉樹中的記錄也包括移動(dòng)對象接下來一段時(shí)間的速度矢量。哈希表的每個(gè)記錄里包含指向歷史軌跡鏈表頭的指針和四叉樹葉子節(jié)點(diǎn)的指針。當(dāng)移動(dòng)對象的速度發(fā)生改變時(shí)，即將上一段軌跡存入哈希表，然后更新四叉樹。更新四叉樹的時(shí)候可能需要修改記錄在四叉樹中的位置，并有可能導(dǎo)致四叉樹節(jié)點(diǎn)的分裂或合并。如果試圖查詢某時(shí)刻某對象的位置，就要判斷查詢時(shí)刻與當(dāng)前時(shí)間的位置。如果查詢時(shí)刻是當(dāng)前或者未來，則查找四叉樹；如果查詢時(shí)刻是過去，則在哈希表中查找。如果給出一個(gè)時(shí)間窗一個(gè)空間窗，同樣需要判斷查詢時(shí)間與當(dāng)前時(shí)間的關(guān)系。查詢時(shí)需要遍歷整個(gè)哈希表和整個(gè)四叉樹中的所有移動(dòng)對象。另外，由于有哈希表的存在，因此可以支持標(biāo)識查詢。這個(gè)數(shù)據(jù)結(jié)構(gòu)的一個(gè)可取之處是全時(shí)態(tài)性。另外一個(gè)可取之處，也是作者所強(qiáng)調(diào)的，即索引的更新效率高，避免了TPR樹各種復(fù)雜的分裂和更新操作。作者認(rèn)為移動(dòng)對象速度頻繁改變，因此更強(qiáng)調(diào)更新效率。但是這個(gè)數(shù)據(jù)結(jié)構(gòu)的缺點(diǎn)也是明顯的。TPR樹之所以受到推崇，是因?yàn)樗趧澐挚臻g范圍的時(shí)候考慮了移動(dòng)對象的速度矢量。而本文基于四叉樹，空間劃分完全沒有考慮移動(dòng)對象的速度矢量。所以對于空間查詢，本文所述的查詢算法要求遍歷所有移動(dòng)對象。作者也承認(rèn)，本索引查詢性能低于TPR樹。還有一個(gè)小問題，作者對于查詢時(shí)間的處理上，要求判斷查詢時(shí)間與當(dāng)前時(shí)間的關(guān)系，這可能會導(dǎo)致錯(cuò)誤。如果一個(gè)移動(dòng)對象在2秒前更新，要求查詢其1秒前的位置，正確的做法是查詢四叉樹，但是按照文中所述會去查詢哈希表。解決這一問題的正確做法是判斷查詢時(shí)間與相應(yīng)移動(dòng)對象最后一次更新的前后關(guān)系。但不同移動(dòng)對象的最后一次更新時(shí)間不同，這樣一來，似乎表明應(yīng)該在哈希表里存儲移動(dòng)對象的最后更新時(shí)間。這個(gè)數(shù)據(jù)結(jié)構(gòu)還有一個(gè)可取之處，即以哈希表存儲所有移動(dòng)對象，然后每個(gè)移動(dòng)對象串一個(gè)歷史軌跡鏈表。這可能是一種比較通用的全時(shí)態(tài)索引思路。

張馭等所著《TPR+-tree：一種面向預(yù)言查詢的有效時(shí)空索引》。文中提出了“雙極值子節(jié)點(diǎn)”的概念。如果n是節(jié)點(diǎn)N中在第d維上速度最大(或最小)的記錄，且n又是N中在第d維上最左(或最右)的記錄，則n被稱為N在第d維上的雙極小(或極大)值子節(jié)點(diǎn)。顯而易見，雙極值子節(jié)點(diǎn)對索引性能的影響比其他子節(jié)點(diǎn)大。相對TPR樹，TPR+樹首先修改插入過程中的算法ChoosePath。TPR樹的算法ChoosePath無法解決這樣一個(gè)問題：如果一個(gè)記錄插入兩個(gè)節(jié)點(diǎn)后兩個(gè)節(jié)點(diǎn)的面積增加值、重疊面積增加值均為0(稱為兩個(gè)節(jié)點(diǎn)均不退化)，那這個(gè)記錄應(yīng)該插入哪個(gè)節(jié)點(diǎn)。TPR+樹提出，當(dāng)遇到這個(gè)問題時(shí)，應(yīng)嘗試消除重疊，消除重疊的方法是對雙極值子節(jié)點(diǎn)執(zhí)行重新插入。簡單來說就是，從不退化的節(jié)點(diǎn)開始向下尋找不退化的子節(jié)點(diǎn)，直至找到葉節(jié)點(diǎn)或一個(gè)節(jié)點(diǎn)中的所有子節(jié)點(diǎn)均不退化；然后對每個(gè)查找路徑末端的子節(jié)點(diǎn)執(zhí)行雙極值子節(jié)點(diǎn)的提取；然后收緊查找路徑上所有節(jié)點(diǎn)的外包矩形，收緊的時(shí)候又要對相應(yīng)節(jié)點(diǎn)執(zhí)行雙極值子節(jié)點(diǎn)的提出和重新插入；最后把查找路徑末端的雙擊值子節(jié)點(diǎn)進(jìn)行重新插入。上述算法在執(zhí)行的時(shí)候有可能導(dǎo)致循環(huán)調(diào)用，此文作者認(rèn)為這種循環(huán)調(diào)用將會使整體的重疊現(xiàn)象得到改善。為避免死循環(huán)，作者也設(shè)置了一些處理規(guī)則。

廖巍等所著《基于速度分布的移動(dòng)對象混合索引方法》。文中提出了HVTPR樹(Hybrid Velocity

distribution based Time-Parameterized

R-tree，基于混合速度分布的TPR樹)。由于速度的不同是導(dǎo)致TPR樹性能惡化的主要原因，所以HVTPR樹先設(shè)置了一個(gè)速度桶鏈表，鏈表中的每個(gè)節(jié)點(diǎn)代表一個(gè)速度域、每個(gè)節(jié)點(diǎn)指向一個(gè)TPR樹。這就使得同一個(gè)TPR樹中的所有對象有相近的速度，從而避免索引性能惡化。速度桶中也包含MBR與VBR，從而使得在查詢的時(shí)候不必遍歷所有的TPR樹。另一方面，HVTPR樹將所有對象存入一個(gè)哈希表中，用于定位對象在HVTPR樹葉節(jié)點(diǎn)中的位置。HVTPR樹支持自低向上更新，因此樹中的每個(gè)節(jié)點(diǎn)都有一個(gè)指向父節(jié)點(diǎn)的指針。所謂自底向上更新是指，當(dāng)更新的時(shí)候，首先根據(jù)哈希表找到葉節(jié)點(diǎn)進(jìn)行修改，然后沿父指針向上尋找父節(jié)點(diǎn)進(jìn)行修改。這樣就避免了復(fù)雜的堆棧或者遞歸。文中沒有涉及R*樹所描述的強(qiáng)制重插入。但是從算法描述上來看，即使進(jìn)行強(qiáng)制重新插入，也應(yīng)當(dāng)會比較簡單。

何凱濤等所著《動(dòng)態(tài)環(huán)境下移動(dòng)對象索引技術(shù)研究》(廖巍是第三作者，這篇文獻(xiàn)發(fā)表時(shí)間晚于HVTPR樹的文獻(xiàn))。文中提出了ETPR樹(Enhanced

Time-Parameterized

R-tree，強(qiáng)化TPR樹)。這種索引結(jié)構(gòu)同樣采用了HVTPR樹所采用的速度桶概念。插入、刪除、查詢算法也與HVTPR樹類似。本文使用了另外一篇文獻(xiàn)中提出的HBU批裝載技術(shù)，可以根據(jù)索引每層預(yù)期的節(jié)點(diǎn)數(shù)和當(dāng)前層矩形包圍框數(shù)目由底向上構(gòu)建TPR樹。具體做法沒有詳細(xì)講，我也沒有看其引用的那篇文獻(xiàn)。另外本文提出了速度桶的構(gòu)造算法，構(gòu)造的算法要求給定兩個(gè)維度上的速度分布直方圖，并給定速度桶的總數(shù)目K，要求輸出一個(gè)最佳的速度桶構(gòu)造方案。構(gòu)造思路如下。首先，要構(gòu)造K個(gè)速度桶，相當(dāng)于要求把x軸方向(橫向)的所有速度分為Vx組，y軸方向(縱向)的所有速度分為Vy組，并要求Vx*Vy=K。其次，當(dāng)指定一組Vx和Vy以后，就要按照一定的算法分別在x軸和y軸上對速度進(jìn)行分組。以x軸為例。算法已經(jīng)得到了x方向上的速度分布直方圖，并且已經(jīng)知道了要在x軸上分Vx組，如果一共有n個(gè)對象，那么第一組就是直方圖上最左邊的n/Vx個(gè)對象，第二組時(shí)接下來的n/Vx個(gè)對象，如此一直劃分下來形成分組結(jié)果，并返回。返回值是什么尚不清楚，從原理上說似乎應(yīng)當(dāng)是一組VBR。最后需要對若干組返回的速度桶方案進(jìn)行優(yōu)選。文中給出了一個(gè)優(yōu)選公式，但是由于不知道返回值是什么格式，所以這個(gè)公式的含義尚不清楚。如果返回值是一組VBR，那么公式似乎是將VBR對時(shí)間進(jìn)行積分。

廖巍等所著《TPR*樹索引構(gòu)建及其動(dòng)態(tài)維護(hù)方法》。此文又晚于ETPR樹的論文。此文使用了與ETPR樹相仿的由底向上構(gòu)建算法和速度桶計(jì)算方法，不再贅述。本文提出了溢出桶的概念，即插入時(shí)不直接寫入磁盤中，而是先存入內(nèi)存中的溢出桶里，待溢出桶滿后一次性寫入磁盤中。而進(jìn)行查詢時(shí)先查詢溢出桶，再查詢樹。這個(gè)做法的目的顯然是為了減低IO次數(shù)。

廖巍等所著《面向移動(dòng)對象的高效預(yù)測范圍聚集查詢方法》。本文所稱的預(yù)測范圍聚集查詢指查詢時(shí)使用Count、Smut、Avg、Max、Min等SQL函數(shù)，直接返回查詢結(jié)果的統(tǒng)計(jì)值而不是返回一組查詢結(jié)果。此文作者指出，傳統(tǒng)上實(shí)現(xiàn)預(yù)測范圍聚集查詢有兩種途徑，第一是用普通查詢返回一組結(jié)果，然后對結(jié)果進(jìn)行統(tǒng)計(jì)，第二是用抽樣的方法返回近似結(jié)果。作者認(rèn)為這兩種方法都不好，因此構(gòu)建了PRA索引。此文與HVTPR樹的文獻(xiàn)發(fā)表于同年，文中索引的結(jié)構(gòu)也與HVTPR樹十分類似，都是最上層一個(gè)速度桶鏈表，最下層加一個(gè)哈希表存儲對象在葉節(jié)點(diǎn)的位置，樹中的每個(gè)節(jié)點(diǎn)都既有指向子節(jié)點(diǎn)的指針也有指向父節(jié)點(diǎn)的指針。區(qū)別是在速度桶以及每個(gè)節(jié)點(diǎn)中均保存自身的統(tǒng)計(jì)信息，這樣如果查詢矩形包含整個(gè)節(jié)點(diǎn)，就不需要繼續(xù)向下查詢子樹了。索引構(gòu)建算法使用了批裝載技術(shù)，插入刪除算法與HVTPR樹相似，區(qū)別僅在于調(diào)整路徑上的統(tǒng)計(jì)信息。更新算法與HVTPR樹不同，直接采用了先刪除后插入的算法，當(dāng)然刪除的次序是從底向上刪除。為了便于查詢，此文作者提出一個(gè)定理：如果在查詢時(shí)間段內(nèi)一個(gè)MBR四個(gè)頂點(diǎn)都曾落入查詢區(qū)域，那么這個(gè)MBR中的所有點(diǎn)都會在查詢時(shí)間段內(nèi)經(jīng)過查詢區(qū)域。根據(jù)此定理，我們只需計(jì)算每個(gè)節(jié)點(diǎn)的MBR四個(gè)頂點(diǎn)落入查詢區(qū)域的時(shí)間。如果這個(gè)時(shí)間都在查詢時(shí)間段內(nèi)，就沒有必要訪問子節(jié)點(diǎn)了。