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

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

2、環(huán)境中的移動(dòng)對(duì)象數(shù)據(jù)庫(kù)的相關(guān)技術(shù)更具現(xiàn)實(shí)意義，而建立高效的索引機(jī)制是移動(dòng)對(duì)象數(shù)據(jù)庫(kù)的研究重點(diǎn)。目前，成熟的索引結(jié)構(gòu)只能實(shí)現(xiàn)移動(dòng)對(duì)象的歷史軌跡和實(shí)時(shí)位置查詢，不能預(yù)測(cè)移動(dòng)對(duì)象在將來(lái)時(shí)刻的位置信息，更不能實(shí)現(xiàn)移動(dòng)對(duì)象的最近鄰查詢。
　　 本文在介紹移動(dòng)對(duì)象數(shù)據(jù)庫(kù)和數(shù)據(jù)模型的基礎(chǔ)上，著重分析了交通路網(wǎng)模型和移動(dòng)對(duì)象索引技術(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)對(duì)象全時(shí)態(tài)位置信息并支持最近鄰查詢的索引結(jié)構(gòu)CRS(AComprehensiveindexingonroadsectors)。CRS為兩層索引結(jié)構(gòu)，上層主要對(duì)交通路網(wǎng)建立索引，下層主要針對(duì)路網(wǎng)上的移動(dòng)對(duì)象建立索引。上層路網(wǎng)以路徑為基本劃分單位，建立路徑2DR樹(shù)，為提高查詢效率，引入路徑哈希表，通過(guò)路徑哈希表可直接定位R樹(shù)的葉子結(jié)點(diǎn)，而無(wú)需搜索整個(gè)上層R樹(shù)才能找到相應(yīng)路徑;為了提高將來(lái)時(shí)刻位置預(yù)測(cè)精

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