1、隨著無線通訊技術(shù)與定位技術(shù)的不斷發(fā)展，對移動對象的跟蹤和定位變得越來越可行。一些新的應(yīng)用，如交通控制、生物保護、氣象監(jiān)視等都涉及到對連續(xù)移動對象的存儲、查詢與處理需求，這就需要移動對象數(shù)據(jù)庫技術(shù)提供支持。移動對象數(shù)據(jù)庫是指對移動對象的位置及其它相關(guān)信息進行表示與處理的數(shù)據(jù)庫。位置相關(guān)的查詢則是移動數(shù)據(jù)庫系統(tǒng)最重要的功能之一。位置相關(guān)的查詢（LDQ：Location Dependent Query）是指查詢結(jié)果依賴于移動用戶的當前位置的查

2、詢。同一個查詢請求，提交的地點不同，返回的結(jié)果也可能將不同。傳統(tǒng)的空間數(shù)據(jù)庫是基于靜態(tài)對象的，沒有時間維度的信息，這意味著所有的屬性都保持它們上一次顯式更新時的值。而在移動數(shù)據(jù)庫中，移動對象的位置隨時間連續(xù)改變。為了實現(xiàn)對移動對象數(shù)據(jù)庫中大量移動對象的時空信息的有效組織和管理，就必須研究適合于移動對象數(shù)據(jù)庫的高效的索引結(jié)構(gòu)與查詢算法。TPR-tree是當前流行的用于查詢移動對象當前及將來某一時刻位置信息的索引結(jié)構(gòu)。由于加入了速度矢量屬性

3、，與傳統(tǒng)的空間索引結(jié)構(gòu)相比TPR-tree更能適應(yīng)移動對象存儲與查詢的需求。
　　 本文分析了移動環(huán)境下的最近鄰查詢方法，對移動環(huán)境下支持位置相關(guān)查詢的常用時空索引TPR-tree的索引結(jié)構(gòu)、構(gòu)建過程與更新算法進行了研究，在此基礎(chǔ)上給出了TPR-tree的最近鄰查詢算法。對于同一結(jié)點下的移動對象，如果其速度比較接近，TPR-tree的查詢效率較高，但是TPR-tree在構(gòu)建時忽視了同一方向上速度間存在的大小差異，使通過計算得到的

4、結(jié)點的包含矩形從某時刻開始不再是其子結(jié)點的最小包含矩形，因而可能導(dǎo)致產(chǎn)生大量對于查詢無用的區(qū)域，以致造成查詢效率的降低。針對這一問題，本文在TPR-tree的基礎(chǔ)上提出了一種改進的時空索引結(jié)構(gòu)：VCTPR-tree。VCTPR-tree可以徹底消除這些無用的區(qū)域產(chǎn)生的可能性，從而使查詢時使用的剪枝效率接近最優(yōu)化。具體來說，VCTPR-tree通過引入速度改變時間序列，使結(jié)點的包含矩形始終保持為其子結(jié)點的最小包含矩形。性能分析顯示，與TP