本文關(guān)鍵詞：面向位置服務(wù)的道路網(wǎng)絡(luò)下的汽車索引技術(shù)研究　出處：《電子科技大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： LBS 索引 道路網(wǎng)絡(luò) Morton碼 移動對象數(shù)據(jù)庫

【摘要】：近年來,隨著衛(wèi)星導(dǎo)航定位、無線通信等技術(shù)不斷快速發(fā)展,由此帶來了基于位置服務(wù)應(yīng)用的大量涌現(xiàn)。當下社會交通網(wǎng)絡(luò)的壓力不斷增大,面向道路網(wǎng)絡(luò)的位置服務(wù)應(yīng)用成為國家重點關(guān)注領(lǐng)域同時也被認為是未來國家之間技術(shù)競爭的戰(zhàn)略制高點。移動對象數(shù)據(jù)庫是相關(guān)位置服務(wù)系統(tǒng)中的數(shù)據(jù)管理中樞,而移動對象索引作為移動對象數(shù)據(jù)庫中的關(guān)鍵性核心技術(shù),其性能優(yōu)劣直接影響著移動數(shù)據(jù)庫效率的高低。是一個研究的熱點問題。本文首先于第二章對各類索引進行研究分析,綜述了各種索引的改進策略和性能的優(yōu)劣。第三章中繼而著重考慮了道路網(wǎng)絡(luò)的特點,并以此建立了以路段為基礎(chǔ)的道路路網(wǎng)模型。分析了R-Tree和Quad-Tree作為索引結(jié)構(gòu)的優(yōu)劣勢。并提出基于雙層結(jié)構(gòu)思想的主索引結(jié)構(gòu),分析了Morton編碼和Hilbert編碼的特點,提出基于Morton碼和Patricia樹的輔助索引結(jié)構(gòu)MPT�；谟成湓硖岢鯩orton碼快速編碼算法QMEA。第四章中闡述了第三章中提出的索引結(jié)構(gòu)的相關(guān)算法,第五章中闡述了面向位置查詢服務(wù)的原型系統(tǒng)的設(shè)計與實現(xiàn),第六章中闡述了針對索引結(jié)構(gòu)和編碼算法性能測試的實驗,并對實驗結(jié)果進行分析。論文大致以:索引結(jié)構(gòu)及編碼算法的提出、基于提出的索引結(jié)構(gòu)的相關(guān)算法闡述、原型系統(tǒng)設(shè)計與實現(xiàn)、索引及編碼算法性能評估及實驗結(jié)果分析為線索來組織全文。文本的主要工作為以下幾點:1、針對MON等雙層索引的更新性能和查詢效率不高的缺點,基于雙層結(jié)構(gòu)思想提出主索引結(jié)構(gòu)CNR。添加上層路網(wǎng)哈希表和下層哈希鏈表以提高了索引的操作效率和更新性能。通過融合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碼,并提出基于MPT的近鄰算法,使得索引結(jié)構(gòu)具有快速響應(yīng)近鄰查詢的能力。將二維空間進行劃分,把分塊后的區(qū)域轉(zhuǎn)換為一維編碼,使MPT索引具有高效的區(qū)域查詢能力。分析基于Morton的范圍查詢的誤差來源,并提出解決方案。第六章中的實驗證明MPT比Hash表,Trie樹等主流一維索引結(jié)構(gòu)的查詢速度更快�；贛PT的近鄰搜索算法比基于R-Tree的近鄰搜索算法效率更高。3、基于映射原理提出Morton碼快速編碼算法QMEA,QMEA的算法時間復(fù)雜為常數(shù)階。第六章中的實驗證明。QMEA比基于迭代原理實現(xiàn)的Morton碼編碼算法更具實際應(yīng)用能力,即在道路網(wǎng)絡(luò)查詢中一般使用的編碼長度范圍內(nèi),QMEA算法的編碼效率較優(yōu)。4、設(shè)計并實現(xiàn)面向位置查詢服務(wù)的原型系統(tǒng)。原型系統(tǒng)具有軌跡查詢、范圍查詢、近鄰查詢、單點查詢、軌跡預(yù)測等功能,可以通過模塊化的形式導(dǎo)入索引模塊來測試索引性能。
[Abstract]:In recent years, along with the development of satellite navigation and positioning, wireless communication technology has been rapid development, which brought about the emergence of a large number of location service application based on network traffic. The social pressure is increasing, location service application oriented road network has become the national focus areas are also regarded as strategic point of technology competition between countries in the future. Moving object database is the central position of the system, and the index of moving objects is the key core technology of mobile database, its performance directly affects the efficiency of the mobile database. It is a hot topic in the study. Firstly, in the second chapter of the various index of research and analysis, summarized and improvement strategies the performance index of the pros and cons. The third chapter focuses on the characteristics of the relay and the road network, and builds up the road to Model of road network based. The analysis of R-Tree and Quad-Tree as the index structure of the advantages and disadvantages. And put forward the main index structure based on the idea of double structure, analyzes the characteristics of Morton encoding and Hilbert encoding, the proposed auxiliary index structure MPT. Morton code and Patricia tree based on Morton codes was proposed based on the principle of mapping fast encoding algorithms for QMEA. fourth chapter explains the related algorithm index structure is proposed in the third chapter, the fifth chapter describes the design and implementation of a prototype system for location query service, the sixth chapter expounds the index structure and coding algorithm performance test, and the experimental results are analyzed. This paper is to put forward the index structure and encoding algorithm, this algorithm is related to the indexing structure based on the design and implementation of the prototype system, performance evaluation index and encoding algorithm and experimental result analysis As a clue to the text. The main work is as follows: 1, according to MON double index update performance and query efficiency, the double-layer structure proposed main index structure of CNR. upper and lower network add hash table hash table to improve the efficiency and update performance based on index. Through the integration of operation CNR and Morton code, the CNR has high response ability range query. In the sixth chapter, the experiment proves that CNR is the mainstream network index structure MON update operation efficiency is higher, and the response path query and range query better.2, based on Patricia tree and Morton code presents a one-dimensional index structure (Morton MPT Patricia Tree), through the improved structure of Patricia tree and correlation algorithm to improve the operating efficiency of index, the fusion index structure and Morton code, and proposes the nearest neighbor algorithm based on MPT, it makes the index structure Have the ability to query fast response. The two-dimensional spatial division, converts the block after the area for one-dimensional encoding, MPT index has efficient regional query ability. Analysis of sources of error range of Morton based on the query, and propose solutions. The sixth chapter of the Ming MPT Hash table, Trie tree the mainstream one dimensional index structure queries faster. MPT nearest neighbor search algorithm based on R-Tree nearest neighbor search algorithm with higher efficiency based on the.3 mapping principle proposed QMEA Morton code for fast encoding algorithm based on QMEA algorithm, the time complexity is a constant order. In the sixth chapter of experiments show that.QMEA has more practical application ability than Morton encoding algorithm the iterative principle based on the realization of the code, the encoding length range is generally used in the road network in the query, the QMEA algorithm is better encoding efficiency of.4, the design and implementation of the original query service oriented position The prototype system has the functions of track query, range query, nearest neighbor query, single point query and trajectory prediction. It can test index performance by modularized import index module.

【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：U495;TP311.13

【參考文獻】

相關(guān)期刊論文 前1條

1 宋廣軍;郝忠孝;王麗杰;;一種基于受限網(wǎng)絡(luò)的移動對象索引[J];計算機科學(xué);2009年12期

相關(guān)碩士學(xué)位論文 前1條

1 涂丹丹;移動對象數(shù)據(jù)庫數(shù)據(jù)模型及查詢處理的研究[D];哈爾濱工業(yè)大學(xué);2007年

，

本文編號：1421043