TPR-樹在基于位置服務系統中的應用研究.pdf

1、時空數據庫技術是計算機科學的新興領域。面對著海量的數據，如何在給定的空間及時間范圍內實現對移動對象快速有效地查詢，是實現定位服務、智能交通、數字化戰(zhàn)爭等諸多應用中迫切需要解決的問題。時空索引技術是解決上述問題的關鍵技術。 TPR-樹是一種可以對移動對象當前位置及未來位置進行有效索引的時空索引技術。TPR-樹用TPBR(Time-Parameterized Bounding Reetangle)來近似表示對象，其基本算法和R*-樹

2、類似。TPR-樹不但支持對移動對象將來位置的預測查詢，而且數據存儲量和數據更新頻率都相對較低。但TPR-樹并沒有得到廣泛的應用，主要是因為其存在以下不足：對移動對象預測查詢的精確度不高：TPBR之間的重疊隨著時間的推移而越發(fā)嚴重，從而影響TPR-樹的查詢性能；算法的時間花費較高，不利于系統作出快速的響應。 本文對TPR-樹的性能優(yōu)化進行了研究。首先介紹了時空索引技術研究方面的成果。接著，根據TPR-樹的特性，設計一種可以實現實時

3、查詢以及預測查詢的基于位置服務系統。然后分別從四個方面對TPR-樹進行研究以及改進：(1)通過引入記錄的生命期，過期記錄(expired entries)不再被真正刪除，只是簡單記載過期的時刻，從而使TPR-樹可以應答對移動對象歷史信息的查詢；(2)對TPR-樹所索引的數據對象進行擴展，使得TPR-樹可以管理更為一般的數據對象；(3)提出一種同時考慮移動對象的空間屬性和速度屬性的結點分裂算法，算法在投影定積分值最大的軸上進行分裂，并把某

4、段時間內子結點周長的定積分作為代價函數，不但降低了算法的計算時間，而且使用此算法所建立的TPR-樹的查詢速度也得到了一定的提高；(4)一種可以限制TPBR之間無限重疊的基于距離的結構調整策略，該算法通過強制重插在某個方向上的移動距離超過閾值的移動對象所對應的記錄，從而達到調整TPR-樹整體結構的目的。 實驗表明，與原TPR-樹結點分裂算法相比，改進后的結點分裂算法的計算時間降低了5～8倍，查詢速度至少提高了50％；而且，在此基礎