资源描述:
《一种面向移动导航设备的电子地图空间索引结构99256》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、计算机研究与发展ISSN10001239CN111777TPJournalofComputerResearchandDevelopment44(2):310~316,2007一种面向移动导航设备的电子地图空间索引结构方钰蒋昌俊陈林(同济大学计算机科学与技术系上海200092)(fy618@yahoocom)AnIndexMethodforDigitalMapSpatialDatainMobileNavigationSystemsFangYu,JiangChangjun,andChenLin(Depta
2、rtmentofComputerScienceandTechnology,TongjiUniversity,Shanghai200092)AbstractThedirectapplicationoftraditionalindexstructureslikeRtreeorquadtreetomobilenavigationsystemshassomedisadvantages:!RtreeorHilbertRtreedoesnottakemultiscaleintoaccount,whichresultsin
3、thedataofthesamescalethatarealwaysaccessedtogetherandseparated;∀SomeotherindexstructuresbasedonRtree,suchasreactivetree,MSRtreeorMORtree,supportmultileveldisplay,buttheyarenotsuitableforembeddedsystemduetotheirhighresourcerequirement;and#Quadtreeisinsuffic
4、ientinportrayingthespatialneighborhoodrelationshipbetweendataobjectsPresentedinthispaperisalinearindexstructurebasedonhierarchicalHilbertgridnamedLHHGindexThisindexstructurefollowsthequadpartitiondataorganizationmechanismusedinquadtree,andintroducesanexpendedH
5、ilbertgridtomakethepartitionbothsequentialandhierarchicalThemainadvantagesofsuchindex,whichspeedupdataaccessforembeddedsystemswithlimitedresourceandNANDflashstorydevice,lieinthreeaspectsFirstly,sequentialandsamelevelclustereddataaccessgivesneighbordataonthesam
6、elevelthenearstoragespaceSecondly,theclumpydataaccessincreasestheIOoperationgranularityThirdly,thelinearandoptimizedindexdatastructureprovideshighersearchingefficiencyThetestingresultshowsthattheLHHGindexesexceedthetraditionalspatialindexinspaceoccupationrate
7、andsearchoperationperformanceKeywordsnavigationdigitalmap;spatialindex;Hilbertgrid摘要传统的Rtree系列和四叉树系列对数据对象的多级显示没有给予足够的支持,在小比例尺地图的显示过程中,影响了检索效率即使是支持多级显示的Rtree的各种变形,也由于对资源的要求而不能满足嵌入式设备的应用需求针对嵌入式设备数据IO的特点,从地图数据的分级显示、顺序与批量访问、索引数据的优化等多方面入手,提出了一种基于多级Hilbert网格的线
8、性索引结构实验证明该索引结构在空间利用率和查询性能等方面与传统的空间索引技术相比有明显的改善,并在上海市交通信息网格移动交通信息服务终端上获得了良好的实施效果关键词导航电子地图;空间索引;Hilbert网格中图法分类号TP31112移动导航系统设计中的关键问题是电子地图的显示矢量地图的数