一種移動對象的位置索引機制研究.pdf

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

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

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

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