交通路網(wǎng)中移動(dòng)對(duì)象組合索引結(jié)構(gòu)研究.pdf

1、隨著WIFI、3G、GPS等無(wú)線通信技術(shù)的快速發(fā)展，各種具有定位功能的車載設(shè)備、無(wú)線移動(dòng)終端的普及，使得越來(lái)越多的基于移動(dòng)對(duì)象位置的服務(wù)被人們廣泛使用。移動(dòng)對(duì)象的位置時(shí)刻在隨時(shí)間變化，存儲(chǔ)移動(dòng)對(duì)象位置信息的數(shù)據(jù)庫(kù)需要處理移動(dòng)對(duì)象時(shí)間和空間頻繁變化的時(shí)空數(shù)據(jù)。在移動(dòng)對(duì)象數(shù)據(jù)庫(kù)中，移動(dòng)對(duì)象索引技術(shù)是支撐移動(dòng)對(duì)象數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)管理的基礎(chǔ)，是移動(dòng)對(duì)象數(shù)據(jù)庫(kù)管理的核心。本文通過(guò)對(duì)現(xiàn)有的移動(dòng)對(duì)象數(shù)據(jù)庫(kù)技術(shù)與索引技術(shù)的研究，在深入分析了交通路網(wǎng)結(jié)構(gòu)的

2、基礎(chǔ)上，提出一種基于交通路網(wǎng)的有效移動(dòng)對(duì)象軌跡索引結(jié)構(gòu)ETI(EfficientmovingobjectsTrajectoriesIndexing)。
　　 ETI移動(dòng)對(duì)象組合索引主要由上下兩層結(jié)構(gòu)組成，上層為路網(wǎng)索引結(jié)構(gòu)由存儲(chǔ)道路信息的道路哈希表和2DRTree組成，實(shí)現(xiàn)對(duì)路網(wǎng)空間的索引。其中2DR-Tree存儲(chǔ)每條路段的空間范圍信息;道路哈希表存儲(chǔ)每條道路的標(biāo)識(shí)及其所有組成路段信息，同一路段的路段指針和2DR-Tree葉結(jié)點(diǎn)

3、指針指向同一個(gè)下層的1DR-Tree。由于路網(wǎng)的結(jié)構(gòu)相對(duì)固定，道路更新周期長(zhǎng)，頻繁改動(dòng)的幾率較小，所以可以將道路哈希表和2DR-Tree視為靜態(tài)結(jié)構(gòu)來(lái)存儲(chǔ)。下層的索引結(jié)構(gòu)由移動(dòng)對(duì)象哈希表、動(dòng)態(tài)鏈表和1DR-Tree共同構(gòu)成。其中，1DR-Tree存儲(chǔ)與之對(duì)應(yīng)路段的移動(dòng)對(duì)象時(shí)間信息和軌跡信息;移動(dòng)對(duì)象哈希中存儲(chǔ)移動(dòng)對(duì)象的標(biāo)識(shí)和實(shí)時(shí)信息，并通過(guò)鏈表指針與單向鏈表相連;單向鏈表按照更新時(shí)間順序存儲(chǔ)移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡信息。在分析了交通路網(wǎng)中移動(dòng)

4、對(duì)象的運(yùn)動(dòng)規(guī)律基礎(chǔ)上，結(jié)合交通道路的流量大小、繁忙程度的不同，在道路哈希結(jié)構(gòu)和移動(dòng)對(duì)象哈希結(jié)構(gòu)中引入基于緩存的LRU內(nèi)存置換算法，提高道路和移動(dòng)對(duì)象在內(nèi)存中的命中率，減少外存訪問(wèn)次數(shù)，從而提高了索引結(jié)構(gòu)的更新效率，使得ETI索引結(jié)構(gòu)相比傳統(tǒng)的FNR-Tree移動(dòng)對(duì)象索引算法具有更高的索引性能。
　　 最后本文還用T.Brinkhoff基于路網(wǎng)的移動(dòng)對(duì)象數(shù)據(jù)產(chǎn)生器和真實(shí)的Oldenburg交通路網(wǎng)數(shù)據(jù)，模擬產(chǎn)生了移動(dòng)對(duì)象實(shí)驗(yàn)測(cè)試數(shù)