基于NANDFlash的嵌入式GIS地图格式设计及优化

发布时间：2020-04-25 12:11

【摘要】： 随着嵌入式计算的不断发展,NAND作为一种高效的存储设备越来越多的被运用到嵌入式环境中,由于各种硬件和软件性能的不断提高使得GIS也得以在嵌入式环境中得到广泛运用。GIS中决定查询性能的是地图空间数据的索引方式,目前普遍采用的是基于磁盘的R-Tree变种索引,本文在此基础上提出了一种更高效的R-Tree变种索引R~d-Tree,并根据NAND Flash的读写特性对索引树的更新方式做出优化。 本文的主要工作包括以下两点: (1)在分析R~o-Tree的基础上,提出了一种新的索引结构R~d-Tree。R~o-Tree提出了外部节点的概念,就是将节点中离其它孩子节点都比较远的孩子作为外部节点,然后放到上一级节点中,藉此来优化节点的质量,减少节点之间的重叠区域。R~d-Tree是一种基于节点密度的索引结构,节点密度是衡量节点性质的一个指标,R~d-Tree的核心思想就是将密度相近的点组织在一起,而在现实世界中,这些密度相近的节点往往在物理上也是相近的。R~d-Tree在以下几方面对R~o-Tree做了改进:一是改进了插入过程中对外部节点的识别算法,在R~d-Tree中如果将一个子节点插入父节点后并不引起父节点密度的降低,我们认为该节点并不是一个外部节点,该识别算法不仅从逻辑上更契合外部节点定义而且优化了节点的质量,减少了节点中的外部节点数量;二是优化了删除过程,当在删除过程中节点向下溢出时,通过从父节点借入一个外部节点来防止无意义的重新插入;三是提高了查询效率,由于减少了外部节点数量,因此在查询过程中需要比较的次数也会相应减少,对于经典的区域查询,对比R~o-Tree本文在实验部分获得了20%的效率提高。 (2)根据NAND Flash的物理特性引入了日志更新机制。由于NAND是一种write-once设备,直接在原文件上进行更新操作会在NAND中产生大量的垃圾数据,降低NAND使用空间进而导致垃圾回收时的频繁擦除操作。因此本文将地图数据分为源数据文件和更新数据文件,将地图的更新以日志的形式全部追加到更新数据文件的尾部,每次打开地图时,将更新数据提交到源数据上,在内存中生成一棵新的索引树。考虑到效率,本文还研究了地图的紧缩操作,即当更新数据比较多的时候地图重建过程会比较长,将更新提交后的新索引树写回到NAND作为新的源数据文件,并删除更新数据文件。本文对地图紧缩的时机也做了探讨。 通过本文的研究,使得对空间数据的索引更高效,对NAND的使用更加优化,延长了NAND的使用寿命并减少了文件系统的垃圾回收次数。
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：P208;TP368.1

【相似文献】

相关期刊论文 前10条

1 梁金成;郭亚友;;Shape格式地图数据加密解密的处理方法[J];测绘标准化;2006年03期

2 闵连权;;矢量地图数据的数字水印技术[J];测绘通报;2007年01期

3 万岳武,赵勇,余鹏;城市框架电子地图数据及其应用[J];北京测绘;2005年02期

4 Dolphin;Jack;;道道通2010年春季版地图数据 为世博之旅添翼[J];音响改装技术;2010年05期

5 吕武，，张国生;区域地下水信息管理系统研究[J];测绘学院学报;1995年01期

6 王同合;GIS应用中海量地图数据的组织[J];测绘学院学报;2001年02期

7 廖义杰,余洁,刘继琳;基于出版的地图数据向GIS空间数据转换的方法探讨[J];测绘通报;2004年03期

8 崔铁军,董延春;地图数据的空间关系与数据模型[J];测绘学院学报;2000年03期

9 王桥;一种新的地图数据检索方法及其应用软件[J];武汉大学学报(信息科学版);1993年04期

10 谭庆全;尹东兵;;浅谈Google Maps地图数据在地震应急中的应用[J];城市与减灾;2010年06期

相关会议论文 前10条

1 肖珂;郭永超;郭书军;;基于MTD的NAND Flash驱动开发[A];2010通信理论与技术新发展——第十五届全国青年通信学术会议论文集（上册）[C];2010年

2 龚一为;曾真;梅懿芳;;基于Flex的Web地图发布技术在湖北地图网中的应用研究[A];中国测绘学会2010年学术年会论文集[C];2010年

3 曹正玉;徐建新;;镇江市天地图数据体系建设[A];江苏省测绘学会2011年学术年会论文集[C];2011年

4 韦胜;;基于瓦片地图访问的规划辅助软件设计[A];转型与重构——2011中国城市规划年会论文集[C];2011年

5 郭御风;李琼;刘光明;张磊;;基于NAND闪存的固态盘技术研究[A];第15届全国信息存储技术学术会议论文集[C];2008年

6 王会娜;丁龙远;顾竹;余聪;;江苏省地图网的数据建设[A];第十三届华东六省一市测绘学会学术交流会论文集[C];2011年

7 刘洪江;李锡坚;王泉;;杭州市地图数据坐标系统快速转换方法的研究与实现[A];第三届长三角科技论坛（测绘分论坛）暨'2006江苏省测绘学术年会论文集[C];2006年

8 ;Design and Implement NAND FLASH Data Storage System Based on the ARM[A];全国数字媒体技术专业建设与人才培养研讨会论文集[C];2011年

9 李擰;李丽;孔晓红;刘飞平;;云南省系列比例尺地理底图的设计与实现[A];第二届“测绘科学前沿技术论坛”论文精选[C];2010年

10 赵姗;李宏伟;蓝士斌;;VC环境下利用DOM存取WebGIS中XML格式地图数据[A];中国地理信息系统协会第八届年会论文集[C];2004年

相关重要报纸文章 前10条

1 本报记者 赵亚辉;“天地图”正式上线 公众可免费使用[N];人民日报;2011年

2 刘葵;Go2map普查地图数据[N];通信产业报;2000年

3 凡妮;高德推出在线地图服务新模式[N];电脑商报;2010年

4 记者 董子凡;我国推出高精度地图快速定制服务[N];科技日报;2011年

5 IT业人士 龙威廉;勿让“天地图”成绿坝第二[N];东方早报;2010年

6 凡歌;“天地图”问题不大[N];中国文化报;2010年

7 国家测绘局地图技术审查中心主任 李朋德;互联网地图:监管和服务并重[N];计算机世界;2009年

8 本报记者 刘方远;以LBS的名义：高德“移动”地图[N];21世纪经济报道;2011年

9 菅建华;浙江完成“天地图”分节点建设试点[N];中国测绘报;2011年

10 本报记者 王玉玲;赤橙黄绿青蓝紫 谁持彩练当空舞[N];中国测绘报;2011年

相关博士学位论文 前10条

1 冯涛;专题地图自动化制作的控制技术研究[D];解放军信息工程大学;2011年

2 郭新成;拓扑地图模型与图库一体化研究[D];长安大学;2011年

3 余辉龙;CMOS一体化相机关键技术研究[D];中国科学院研究生院（长春光学精密机械与物理研究所）;2010年

4 尹章才;地图表达机制及其基于可扩展标记语言的描述[D];武汉大学;2005年

5 蔡伯根;低成本列控系统的列车组合定位理论与方法[D];北京交通大学;2010年

6 赵彬彬;多尺度矢量地图空间目标匹配方法及其应用研究[D];中南大学;2011年

7 孙建国;基于内容特征的二维矢量地图数字水印技术研究[D];哈尔滨工程大学;2009年

8 杨铁利;GIS地图产品的不确定性研究[D];吉林大学;2007年

9 周e

本文编号：2640230