結(jié)合時間和空間數(shù)據(jù)的移動對象數(shù)據(jù)索引PM-tree

　　隨著移動定位技術(shù)和無線通訊技術(shù)發(fā)展，移動對象的應(yīng)用領(lǐng)域越來越廣闊。位置隨時間而變化的移動對象產(chǎn)生的時空數(shù)據(jù)具有規(guī)模大、多維性、結(jié)構(gòu)復(fù)雜和關(guān)系復(fù)雜等特點(diǎn)。由于移動對象的運(yùn)動軌跡大多被限定在特定的交通網(wǎng)絡(luò)中，因此基于路網(wǎng)的移動對象索引成為時空數(shù)據(jù)索引研究的一個重要應(yīng)用分支。目前，針對移動對象歷史數(shù)據(jù)的區(qū)域査詢優(yōu)化的研究重點(diǎn)是如何提高窗口査詢的效率。這類索引通常以同一線路為單位來組織軌跡數(shù)據(jù)的存儲。索引通常采用兩層的 R-tree索引結(jié)構(gòu)，上層的2 Dr-tree用于索引在某個區(qū)域內(nèi)的線路，下層的2DR-tree用于索引某個時間段內(nèi)在這些區(qū)域的移動對象。這類索引在處理軌跡信息的時間維度的時候，僅僅是把時間維度等同于空間的維度來進(jìn)行R樹維度的擴(kuò)展。由于R樹算法不能有效地降低最小限定矩形的空間堆疊問題，尤其是在數(shù)據(jù)量較大、數(shù)據(jù)維數(shù)增加時表現(xiàn)得更為明顯。所以，為了提高路網(wǎng)中移動對象時空信息的存儲以及査詢的效率本文則將軌跡信息中的時間數(shù)據(jù)和空間數(shù)據(jù)整合起來，提出了一種移動對象數(shù)據(jù)索引PM-tree（ Phase- point Mg Object tree）。首先運(yùn)用映射函數(shù)把路網(wǎng)中移動對象運(yùn)動軌跡的二維時空矩形投影成帶參數(shù)的一維“時空相點(diǎn)”，并討論了時空相點(diǎn)之間的偏序關(guān)系，建立了基于相點(diǎn)偏序劃分的相點(diǎn)序分枝結(jié)構(gòu)，為索引的建立提供了理論支撐。接著論文以MON-tre索引為基礎(chǔ)，以梖點(diǎn)序分枝結(jié)構(gòu)來改進(jìn)其下層索引結(jié)構(gòu)，提出了時空相點(diǎn)移動對象數(shù)據(jù)索引，該索引能完成運(yùn)動軌跡時空的一體化查詢，能避免類 R-tree索引中最小限定矩形堆疊導(dǎo)致的效率低下的問題，有效地縮小搜索空間。最后論文實現(xiàn)了索引的贈量式動態(tài)更新管理。通過實驗的對比分析，表明 Pm-tree索引不但能有效提高儲存空間的利用率，一次一集合”的查洵模式還提高了查詢性能。