面向位置服務(wù)的道路網(wǎng)絡(luò)下的汽車索引技術(shù)研究.pdf

1、近年來，隨著衛(wèi)星導(dǎo)航定位、無線通信等技術(shù)不斷快速發(fā)展，由此帶來了基于位置服務(wù)應(yīng)用的大量涌現(xiàn)。當(dāng)下社會交通網(wǎng)絡(luò)的壓力不斷增大，面向道路網(wǎng)絡(luò)的位置服務(wù)應(yīng)用成為國家重點(diǎn)關(guān)注領(lǐng)域同時也被認(rèn)為是未來國家之間技術(shù)競爭的戰(zhàn)略制高點(diǎn)。移動對象數(shù)據(jù)庫是相關(guān)位置服務(wù)系統(tǒng)中的數(shù)據(jù)管理中樞，而移動對象索引作為移動對象數(shù)據(jù)庫中的關(guān)鍵性核心技術(shù)，其性能優(yōu)劣直接影響著移動數(shù)據(jù)庫效率的高低。是一個研究的熱點(diǎn)問題。
　　本文首先于第二章對各類索引進(jìn)行研究分析，綜述

2、了各種索引的改進(jìn)策略和性能的優(yōu)劣。第三章中繼而著重考慮了道路網(wǎng)絡(luò)的特點(diǎn)，并以此建立了以路段為基礎(chǔ)的道路路網(wǎng)模型。分析了R-Tree和Quad-Tree作為索引結(jié)構(gòu)的優(yōu)劣勢。并提出基于雙層結(jié)構(gòu)思想的主索引結(jié)構(gòu)，分析了Morton編碼和Hilbert編碼的特點(diǎn)，提出基于 Morton碼和 Patricia樹的輔助索引結(jié)構(gòu) MPT。基于映射原理提出 Morton碼快速編碼算法 QMEA。第四章中闡述了第三章中提出的索引結(jié)構(gòu)的相關(guān)算法，第五章中

3、闡述了面向位置查詢服務(wù)的原型系統(tǒng)的設(shè)計與實現(xiàn)，第六章中闡述了針對索引結(jié)構(gòu)和編碼算法性能測試的實驗，并對實驗結(jié)果進(jìn)行分析。論文大致以：索引結(jié)構(gòu)及編碼算法的提出、基于提出的索引結(jié)構(gòu)的相關(guān)算法闡述、原型系統(tǒng)設(shè)計與實現(xiàn)、索引及編碼算法性能評估及實驗結(jié)果分析為線索來組織全文。
　　文本的主要工作為以下幾點(diǎn)：
　　1、針對MON等雙層索引的更新性能和查詢效率不高的缺點(diǎn)，基于雙層結(jié)構(gòu)思想提出主索引結(jié)構(gòu) CNR。添加上層路網(wǎng)哈希表和下層哈希

4、鏈表以提高了索引的操作效率和更新性能。通過融合CNR和Morton碼，使得CNR具有高效響應(yīng)范圍查詢的能力。第六章中的實驗證明CNR較主流路網(wǎng)索引結(jié)構(gòu)MON的更新操作效率更高，且響應(yīng)軌跡查詢和范圍查詢的能力更佳。
　　2、基于Patricia樹和Morton碼提出一種一維索引結(jié)構(gòu)MPT（Morton Patricia Tree），通過改良Patricia樹的結(jié)構(gòu)和相關(guān)算法以提高索引的操作效率，融合索引結(jié)構(gòu)和Morton碼，并提出基

5、于MPT的近鄰算法，使得索引結(jié)構(gòu)具有快速響應(yīng)近鄰查詢的能力。將二維空間進(jìn)行劃分，把分塊后的區(qū)域轉(zhuǎn)換為一維編碼，使MPT索引具有高效的區(qū)域查詢能力。分析基于Morton的范圍查詢的誤差來源，并提出解決方案。第六章中的實驗證明MPT比Hash表，Trie樹等主流一維索引結(jié)構(gòu)的查詢速度更快。基于MPT的近鄰搜索算法比基于R-Tree的近鄰搜索算法效率更高。
　　3、基于映射原理提出Morton碼快速編碼算法QMEA，QMEA的算法時間復(fù)