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

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