【摘要】： 隨著嵌入式計算的不斷發(fā)展,NAND作為一種高效的存儲設(shè)備越來越多的被運用到嵌入式環(huán)境中,由于各種硬件和軟件性能的不斷提高使得GIS也得以在嵌入式環(huán)境中得到廣泛運用。GIS中決定查詢性能的是地圖空間數(shù)據(jù)的索引方式,目前普遍采用的是基于磁盤的R-Tree變種索引,本文在此基礎(chǔ)上提出了一種更高效的R-Tree變種索引R~d-Tree,并根據(jù)NAND Flash的讀寫特性對索引樹的更新方式做出優(yōu)化。 本文的主要工作包括以下兩點: (1)在分析R~o-Tree的基礎(chǔ)上,提出了一種新的索引結(jié)構(gòu)R~d-Tree。R~o-Tree提出了外部節(jié)點的概念,就是將節(jié)點中離其它孩子節(jié)點都比較遠的孩子作為外部節(jié)點,然后放到上一級節(jié)點中,藉此來優(yōu)化節(jié)點的質(zhì)量,減少節(jié)點之間的重疊區(qū)域。R~d-Tree是一種基于節(jié)點密度的索引結(jié)構(gòu),節(jié)點密度是衡量節(jié)點性質(zhì)的一個指標,R~d-Tree的核心思想就是將密度相近的點組織在一起,而在現(xiàn)實世界中,這些密度相近的節(jié)點往往在物理上也是相近的。R~d-Tree在以下幾方面對R~o-Tree做了改進:一是改進了插入過程中對外部節(jié)點的識別算法,在R~d-Tree中如果將一個子節(jié)點插入父節(jié)點后并不引起父節(jié)點密度的降低,我們認為該節(jié)點并不是一個外部節(jié)點,該識別算法不僅從邏輯上更契合外部節(jié)點定義而且優(yōu)化了節(jié)點的質(zhì)量,減少了節(jié)點中的外部節(jié)點數(shù)量;二是優(yōu)化了刪除過程,當在刪除過程中節(jié)點向下溢出時,通過從父節(jié)點借入一個外部節(jié)點來防止無意義的重新插入;三是提高了查詢效率,由于減少了外部節(jié)點數(shù)量,因此在查詢過程中需要比較的次數(shù)也會相應(yīng)減少,對于經(jīng)典的區(qū)域查詢,對比R~o-Tree本文在實驗部分獲得了20%的效率提高。 (2)根據(jù)NAND Flash的物理特性引入了日志更新機制。由于NAND是一種write-once設(shè)備,直接在原文件上進行更新操作會在NAND中產(chǎn)生大量的垃圾數(shù)據(jù),降低NAND使用空間進而導(dǎo)致垃圾回收時的頻繁擦除操作。因此本文將地圖數(shù)據(jù)分為源數(shù)據(jù)文件和更新數(shù)據(jù)文件,將地圖的更新以日志的形式全部追加到更新數(shù)據(jù)文件的尾部,每次打開地圖時,將更新數(shù)據(jù)提交到源數(shù)據(jù)上,在內(nèi)存中生成一棵新的索引樹。考慮到效率,本文還研究了地圖的緊縮操作,即當更新數(shù)據(jù)比較多的時候地圖重建過程會比較長,將更新提交后的新索引樹寫回到NAND作為新的源數(shù)據(jù)文件,并刪除更新數(shù)據(jù)文件。本文對地圖緊縮的時機也做了探討。 通過本文的研究,使得對空間數(shù)據(jù)的索引更高效,對NAND的使用更加優(yōu)化,延長了NAND的使用壽命并減少了文件系統(tǒng)的垃圾回收次數(shù)。
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2010
【分類號】：P208;TP368.1

【相似文獻】

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

1 梁金成;郭亞友;;Shape格式地圖數(shù)據(jù)加密解密的處理方法[J];測繪標準化;2006年03期

2 閔連權(quán);;矢量地圖數(shù)據(jù)的數(shù)字水印技術(shù)[J];測繪通報;2007年01期

3 萬岳武,趙勇,余鵬;城市框架電子地圖數(shù)據(jù)及其應(yīng)用[J];北京測繪;2005年02期

4 Dolphin;Jack;;道道通2010年春季版地圖數(shù)據(jù) 為世博之旅添翼[J];音響改裝技術(shù);2010年05期

5 呂武，，張國生;區(qū)域地下水信息管理系統(tǒng)研究[J];測繪學(xué)院學(xué)報;1995年01期

6 王同合;GIS應(yīng)用中海量地圖數(shù)據(jù)的組織[J];測繪學(xué)院學(xué)報;2001年02期

7 廖義杰,余潔,劉繼琳;基于出版的地圖數(shù)據(jù)向GIS空間數(shù)據(jù)轉(zhuǎn)換的方法探討[J];測繪通報;2004年03期

8 崔鐵軍,董延春;地圖數(shù)據(jù)的空間關(guān)系與數(shù)據(jù)模型[J];測繪學(xué)院學(xué)報;2000年03期

9 王橋;一種新的地圖數(shù)據(jù)檢索方法及其應(yīng)用軟件[J];武漢大學(xué)學(xué)報(信息科學(xué)版);1993年04期

10 譚慶全;尹東兵;;淺談Google Maps地圖數(shù)據(jù)在地震應(yīng)急中的應(yīng)用[J];城市與減災(zāi);2010年06期

相關(guān)會議論文 前10條

1 肖珂;郭永超;郭書軍;;基于MTD的NAND Flash驅(qū)動開發(fā)[A];2010通信理論與技術(shù)新發(fā)展——第十五屆全國青年通信學(xué)術(shù)會議論文集（上冊）[C];2010年

2 龔一為;曾真;梅懿芳;;基于Flex的Web地圖發(fā)布技術(shù)在湖北地圖網(wǎng)中的應(yīng)用研究[A];中國測繪學(xué)會2010年學(xué)術(shù)年會論文集[C];2010年

3 曹正玉;徐建新;;鎮(zhèn)江市天地圖數(shù)據(jù)體系建設(shè)[A];江蘇省測繪學(xué)會2011年學(xué)術(shù)年會論文集[C];2011年

4 韋勝;;基于瓦片地圖訪問的規(guī)劃輔助軟件設(shè)計[A];轉(zhuǎn)型與重構(gòu)——2011中國城市規(guī)劃年會論文集[C];2011年

5 郭御風(fēng);李瓊;劉光明;張磊;;基于NAND閃存的固態(tài)盤技術(shù)研究[A];第15屆全國信息存儲技術(shù)學(xué)術(shù)會議論文集[C];2008年

6 王會娜;丁龍遠;顧竹;余聰;;江蘇省地圖網(wǎng)的數(shù)據(jù)建設(shè)[A];第十三屆華東六省一市測繪學(xué)會學(xué)術(shù)交流會論文集[C];2011年

7 劉洪江;李錫堅;王泉;;杭州市地圖數(shù)據(jù)坐標系統(tǒng)快速轉(zhuǎn)換方法的研究與實現(xiàn)[A];第三屆長三角科技論壇（測繪分論壇）暨'2006江蘇省測繪學(xué)術(shù)年會論文集[C];2006年

8 ;Design and Implement NAND FLASH Data Storage System Based on the ARM[A];全國數(shù)字媒體技術(shù)專業(yè)建設(shè)與人才培養(yǎng)研討會論文集[C];2011年

9 李擰;李麗;孔曉紅;劉飛平;;云南省系列比例尺地理底圖的設(shè)計與實現(xiàn)[A];第二屆“測繪科學(xué)前沿技術(shù)論壇”論文精選[C];2010年

10 趙姍;李宏偉;藍士斌;;VC環(huán)境下利用DOM存取WebGIS中XML格式地圖數(shù)據(jù)[A];中國地理信息系統(tǒng)協(xié)會第八屆年會論文集[C];2004年

相關(guān)重要報紙文章 前10條

1 本報記者 趙亞輝;“天地圖”正式上線 公眾可免費使用[N];人民日報;2011年

2 劉葵;Go2map普查地圖數(shù)據(jù)[N];通信產(chǎn)業(yè)報;2000年

3 凡妮;高德推出在線地圖服務(wù)新模式[N];電腦商報;2010年

4 記者 董子凡;我國推出高精度地圖快速定制服務(wù)[N];科技日報;2011年

5 IT業(yè)人士 龍威廉;勿讓“天地圖”成綠壩第二[N];東方早報;2010年

6 凡歌;“天地圖”問題不大[N];中國文化報;2010年

7 國家測繪局地圖技術(shù)審查中心主任 李朋德;互聯(lián)網(wǎng)地圖:監(jiān)管和服務(wù)并重[N];計算機世界;2009年

8 本報記者 劉方遠;以LBS的名義：高德“移動”地圖[N];21世紀經(jīng)濟報道;2011年

9 菅建華;浙江完成“天地圖”分節(jié)點建設(shè)試點[N];中國測繪報;2011年

10 本報記者 王玉玲;赤橙黃綠青藍紫 誰持彩練當空舞[N];中國測繪報;2011年

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

1 馮濤;專題地圖自動化制作的控制技術(shù)研究[D];解放軍信息工程大學(xué);2011年

2 郭新成;拓撲地圖模型與圖庫一體化研究[D];長安大學(xué);2011年

3 余輝龍;CMOS一體化相機關(guān)鍵技術(shù)研究[D];中國科學(xué)院研究生院（長春光學(xué)精密機械與物理研究所）;2010年

4 尹章才;地圖表達機制及其基于可擴展標記語言的描述[D];武漢大學(xué);2005年

5 蔡伯根;低成本列控系統(tǒng)的列車組合定位理論與方法[D];北京交通大學(xué);2010年

6 趙彬彬;多尺度矢量地圖空間目標匹配方法及其應(yīng)用研究[D];中南大學(xué);2011年

7 孫建國;基于內(nèi)容特征的二維矢量地圖數(shù)字水印技術(shù)研究[D];哈爾濱工程大學(xué);2009年

8 楊鐵利;GIS地圖產(chǎn)品的不確定性研究[D];吉林大學(xué);2007年

9 周e

本文編號：2640230