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

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.