TPR-樹在基于位置服務(wù)系統(tǒng)中的應(yīng)用研究.pdf

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

2、類似。TPR-樹不但支持對移動對象將來位置的預(yù)測查詢，而且數(shù)據(jù)存儲量和數(shù)據(jù)更新頻率都相對較低。但TPR-樹并沒有得到廣泛的應(yīng)用，主要是因?yàn)槠浯嬖谝韵虏蛔悖簩σ苿訉ο箢A(yù)測查詢的精確度不高：TPBR之間的重疊隨著時(shí)間的推移而越發(fā)嚴(yán)重，從而影響TPR-樹的查詢性能；算法的時(shí)間花費(fèi)較高，不利于系統(tǒng)作出快速的響應(yīng)。 本文對TPR-樹的性能優(yōu)化進(jìn)行了研究。首先介紹了時(shí)空索引技術(shù)研究方面的成果。接著，根據(jù)TPR-樹的特性，設(shè)計(jì)一種可以實(shí)現(xiàn)實(shí)時(shí)

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

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