一種移動(dòng)對象的位置索引機(jī)制研究.pdf

1、隨著移動(dòng)設(shè)備、無線通信和GPS的大量應(yīng)用，催生了一類基于位置的服務(wù)(Locationbasedservice)。位置服務(wù)提供給查詢者關(guān)于移動(dòng)對象隨時(shí)間變化的位置信息，數(shù)據(jù)庫需要處理不斷頻繁更新的時(shí)空數(shù)據(jù)，而傳統(tǒng)數(shù)據(jù)庫一般只能處理更新周期比較長的數(shù)據(jù)，無法響應(yīng)數(shù)據(jù)的頻繁更新，因此時(shí)空數(shù)據(jù)庫應(yīng)運(yùn)而生。在現(xiàn)實(shí)環(huán)境中，大多數(shù)的移動(dòng)對象在二維空間中做受限運(yùn)動(dòng)（公交車在交通道路上按公交路線行駛），而不是自由運(yùn)動(dòng)（輪船在大海中自由航行），因此研究受限

2、環(huán)境中的移動(dòng)對象數(shù)據(jù)庫的相關(guān)技術(shù)更具現(xiàn)實(shí)意義，而建立高效的索引機(jī)制是移動(dòng)對象數(shù)據(jù)庫的研究重點(diǎn)。目前，成熟的索引結(jié)構(gòu)只能實(shí)現(xiàn)移動(dòng)對象的歷史軌跡和實(shí)時(shí)位置查詢，不能預(yù)測移動(dòng)對象在將來時(shí)刻的位置信息，更不能實(shí)現(xiàn)移動(dòng)對象的最近鄰查詢。
　　 本文在介紹移動(dòng)對象數(shù)據(jù)庫和數(shù)據(jù)模型的基礎(chǔ)上，著重分析了交通路網(wǎng)模型和移動(dòng)對象索引技術(shù)，首先考慮交通路網(wǎng)拓?fù)浣Y(jié)構(gòu)，采用路徑為基本單位，離散的表示路網(wǎng)信息;然后借鑒兩種常用索引結(jié)構(gòu)FNR-Tree和MO

3、N-Tree的優(yōu)點(diǎn)，提出一種能夠索引移動(dòng)對象全時(shí)態(tài)位置信息并支持最近鄰查詢的索引結(jié)構(gòu)CRS(AComprehensiveindexingonroadsectors)。CRS為兩層索引結(jié)構(gòu)，上層主要對交通路網(wǎng)建立索引，下層主要針對路網(wǎng)上的移動(dòng)對象建立索引。上層路網(wǎng)以路徑為基本劃分單位，建立路徑2DR樹，為提高查詢效率，引入路徑哈希表，通過路徑哈希表可直接定位R樹的葉子結(jié)點(diǎn)，而無需搜索整個(gè)上層R樹才能找到相應(yīng)路徑;為了提高將來時(shí)刻位置預(yù)測精

4、度和有效的支持最近鄰查詢，在上層索引結(jié)構(gòu)中引入了交叉口轉(zhuǎn)向表，記錄路徑上所有交叉點(diǎn)的信息。下層結(jié)構(gòu)主要由移動(dòng)對象2DR樹、靜態(tài)對象1DR樹、移動(dòng)對象哈希表和動(dòng)態(tài)鏈表組成，上層R樹的每個(gè)葉子結(jié)點(diǎn)都指向一棵移動(dòng)對象R樹和靜態(tài)對象R樹，移動(dòng)對象R樹記錄了該條路徑上所有的移動(dòng)對象位置信息，靜態(tài)對象R樹記錄了該條路徑上所有的靜態(tài)對象，且每個(gè)靜態(tài)對象都指向一條最近鄰鏈表（NNL），用于實(shí)現(xiàn)移動(dòng)對象相對靜態(tài)對象的最近鄰查詢。為了提高索引移動(dòng)對象軌跡信