面向位置服務的道路網絡下的汽車索引技術研究.pdf

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

2、了各種索引的改進策略和性能的優(yōu)劣。第三章中繼而著重考慮了道路網絡的特點，并以此建立了以路段為基礎的道路路網模型。分析了R-Tree和Quad-Tree作為索引結構的優(yōu)劣勢。并提出基于雙層結構思想的主索引結構，分析了Morton編碼和Hilbert編碼的特點，提出基于 Morton碼和 Patricia樹的輔助索引結構 MPT?；谟成湓硖岢?Morton碼快速編碼算法 QMEA。第四章中闡述了第三章中提出的索引結構的相關算法，第五章中

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

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

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