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

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

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

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