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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 本報(bào)記者 趙亞輝;“天地圖”正式上線 公眾可免費(fèi)使用[N];人民日?qǐng)?bào);2011年

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

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

4 記者 董子凡;我國(guó)推出高精度地圖快速定制服務(wù)[N];科技日?qǐng)?bào);2011年

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

6 凡歌;“天地圖”問題不大[N];中國(guó)文化報(bào);2010年

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

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

9 菅建華;浙江完成“天地圖”分節(jié)點(diǎn)建設(shè)試點(diǎn)[N];中國(guó)測(cè)繪報(bào);2011年

10 本報(bào)記者 王玉玲;赤橙黃綠青藍(lán)紫 誰(shuí)持彩練當(dāng)空舞[N];中國(guó)測(cè)繪報(bào);2011年

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

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

2 郭新成;拓?fù)涞貓D模型與圖庫(kù)一體化研究[D];長(zhǎng)安大學(xué);2011年

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

4 尹章才;地圖表達(dá)機(jī)制及其基于可擴(kuò)展標(biāo)記語(yǔ)言的描述[D];武漢大學(xué);2005年

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

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

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

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

9 周e

本文編號(hào)：2640230