高级检索

    一种面向移动导航设备的电子地图空间索引结构

    An Index Method for Digital Map Spatial Data in Mobile Navigation Systems

    • 摘要: 传统的R-tree系列和四叉树系列对数据对象的多级显示没有给予足够的支持,在小比例尺地图的显示过程中,影响了检索效率.即使是支持多级显示的R-tree的各种变形,也由于对资源的要求而不能满足嵌入式设备的应用需求.针对嵌入式设备数据I/O的特点,从地图数据的分级显示、顺序与批量访问、索引数据的优化等多方面入手,提出了一种基于多级Hilbert网格的线性索引结构.实验证明该索引结构在空间利用率和查询性能等方面与传统的空间索引技术相比有明显的改善,并在上海市交通信息网格移动交通信息服务终端上获得了良好的实施效果.

       

      Abstract: The direct application of traditional index structures like R-tree or quad-tree to mobile navigation systems has some disadvantages: ① R-tree or Hilbert-R-tree does not take multi-scale into account, which results in the data of the same scale that are always accessed together and separated; ② Some other index structures based on R-tree, such as reactive-tree, MS-R-tree or MOR-tree, support multi-level display, but they are not suitable for embedded system due to their high resource requirement; and ③ Quad-tree is insufficient in portraying the spatial neighborhood relationship between data objects. Presented in this paper is a linear index structure based on hierarchical Hilbert grid named LHHG index. This index structure follows the quad-partition data organization mechanism used in quad-tree, and introduces an expended Hilbert grid to make the partition both sequential and hierarchical. The main advantages of such index, which speedup data access for embedded systems with limited resource and NAND flash story device, lie in three aspects. Firstly, sequential and same-level-clustered data access gives neighbor data on the same level the near storage space. Secondly, the clumpy data access increases the I/O operation granularity. Thirdly, the linear and optimized index data structure provides higher searching efficiency. The testing result shows that the LHHG indexes exceed the traditional spatial index in space occupation rate and search operation performance.

       

    /

    返回文章
    返回